//img.uscri.be/pth/68b664516c27f74489968d73c311f953238798fe
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

1Parcimonie de Fitch Hartigan pour un arbre donné

4 pages
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


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.