1Parcimonie de Fitch Hartigan pour un arbre donné

Publié par

1Parcimonie de Fitch-Hartigan pour un arbre donné • La parcimonie totale est la somme des parcimonies de chaque site ; on raisonne indépendamment sur chacun. • A chaque nœud x est attaché l'ensemble des valeurs possibles C xa f réalisant la parcimonie optimale P xa f • Soit g xa f et d xa f les fils droit et gauche de x, on a la récurrence : Si g xa f et d xa f , si C g x C d xa fb g a fb g? ≠ ? alors C x C g x C d x( ) = ?a fb g a fb g P x P g x P d x( ) = +a fb g a fb g sinon C x C g x C d x( ) = ?a fb g a fb g P x P g x P d x( ) = + +1 a fb g a fb g Sinon P xa f = 0 et C x xa f k p= valeur de • Le résultat est indépendant de la position de la racine. Le calcul est en O ns?b g (n = nombre de séquences ; s = nombre de sites). Et on peut réaliser les unions et intersections au niveau bit. • Ce parcours est postorder. Un parcours preorder permet d'assigner aux nœuds une valeur réalisant l'optimum.

  • parcimonie

  • parcimonie de sankoff

  • coûts unitaire

  • parcimonie de fitch-hartigan

  • algo de distance elemento

  • ?a fb

  • matrice de coût de substitution

  • minimum de parcimonie


Publié le : mardi 19 juin 2012
Lecture(s) : 29
Tags :
Source : lirmm.fr
Nombre de pages : 4
Voir plus Voir moins
1
Parcimonie de Fitch-Hartigan pour un arbre donné
La parcimonie totale est la somme des parcimonies de chaque
site ; on raisonne indépendamment sur chacun.
A chaque noeud
x
est attaché l’ensemble des valeurs possibles
C
x
a
f
réalisant la parcimonie optimale
P
x
a
f
Soit
g
x
a
f
et
d
x
a
f
les fils droit et gauche de
x
,
o
n
a
l
a
récurrence :
Si
g
x
a
f
et
d
x
a
f
,
s
i
C
g
x
C
d
x
a
f
b
g
a
f
b
g
alors
C
x
C
g
x
C
d
x
(
)
=
a
f
b
g
a
f
b
g
P
x
P
g
x
P
d
x
(
)
=
+
a
f
b
g
a
f
b
g
sinon
C
x
C
g
x
C
d
x
(
)
=
a
f
b
g
a
f
b
g
P
x
P
g
x
P
d
x
(
)
=
+
+
1
a
f
b
g
a
f
b
g
Sinon
P
x
a
f
=
0 et
C
x
x
a
f
k
p
=
valeur de
Le résultat est indépendant de la position de la racine. Le calcul
est en
O
n
s
Σ
b
g
(
n
= nombre de séquences ;
s
= nombre de sites).
Et on peut réaliser les unions et intersections au niveau bit.
Ce parcours est postorder. Un parcours preorder permet
d’assigner aux noeuds une valeur réalisant l’optimum.
2
Parcimonie de Sankoff pour un arbre donné
Le poids des substitutions n’est pas unitaire mais est donné par
une matrice de coûts :
S
XY
A chaque noeud
i
est attaché le vecteur
A
T
G
C
i
i
i
i
,
,
,
a
f
qui
représente le minimum de parcimonie en supposant que le noeud
a pour valeur A, T, G, resp. C.
Soit le noeud 0, père de 1 et 2. On a la formule de récurrence :
A
M
i
n
A
A
S
A
T
S
T
S
G
T
M
i
n
T
T
S
A
T
S
A
A
AT
AT
AG
TA
TA
0
1
2
1
2
1
2
0
1
2
1
2
1
2
2
=
+
+
+
+
+
+
=
+
+
+
+
+
,
,
, ...
,
,
, ...
a
f
a
f
A
A
A
C
G
T
0, , ,
a
f
(0,2,2,2)
(1,1,2,2)
(1,2,3,3)
(2,2,1,1)
(3,4,3,3)
Coût unitaire. La parcimonie est 3.
Le résultat est indépendant de la position de la racine lorsque
S
est
symétrique. Le calcul est en
O
n
s
Σ
3
e
j
.
3
Recherche de tous les meilleurs arbres de duplication simple
(arches) dans le cas des minisatellites
Il y a un seul site
L’alphabet est constitué des variants
On dispose d’une matrice de coût de substitution entre variants
L’algo
de
distance
Elemento&Gascuel
(CPM’03)
est
directement applicable, mais la parcimonie est plus cohérente
avec l’alignement
On va combiner algorithme de Sankoff et EG.
4
A chaque interval
p
q
,
est attaché
A
B
C
D
pq
pq
pq
pq
,
,
,
,
.
.
.
d
i
,
chaque
X
pq
contient quatre informations :
(1)
PX
pq
la valeur de parcimonie optimale pour
X
(2)
MX
pq
l’entier
m*
de
p
q
,
1 réalisant cet optimum
(3)
GX
pq
le caractère de
p
m
,
* réalisant l’optimum
(4)
DX
pq
le caractère de
m
q
*
,
+
1
réalisant l’optimum
On calcule récursivement ces valeurs pour
p
q
,
de taille
croissante :
PX
Max
PY
PZ
S
S
pq
m
p
q
Y
Z
pm
m
q
XY
XZ
=
+
+
+
+
,
,
,
(
)
1
1
Σ
Σ
d
i
Un arbre optimal est composé de sous-arbre optimaux ; la
méthode assure d’avoir au moins une solution optimale pour
chaque interval.
On s’attend à avoir plusieurs solutions optimales, pour
plusieurs caractères et plusieurs positions de la racine. Les
calculs sont pour une part redondants, mais on ne le sait qu’à
la fin (?).
L’algo est en
O
n
3
3
Σ
e
j
.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.