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.
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin