Réarrangement de l'arbre - Tree rearrangement

Les réarrangements d'arbres sont des algorithmes déterministes dédiés à la recherche d'une arborescence optimale . Ils peuvent être appliqués à n'importe quel ensemble de données naturellement arrangées dans un arbre, mais ont la plupart des applications en phylogénétique computationnelle , en particulier dans les recherches de parcimonie maximale et de vraisemblance maximale des arbres phylogénétiques , qui cherchent à identifier l'un parmi de nombreux arbres possibles qui explique le mieux la histoire évolutive d'un gène ou d'une espèce particulière .

Réarrangements d'arborescence de base

  • Échangeur du plus proche voisin (NNI)

  • Élagage et regreffage de sous-arbres (SPR)

  • Bisection et reconnexion d'arbres (TBR)

Le réarrangement d'arbre le plus simple, connu sous le nom d' échange du plus proche voisin , échange la connectivité de quatre sous-arbres au sein de l'arbre principal. Comme il existe trois manières possibles de connecter quatre sous-arbres, et l'une est la connectivité d'origine, chaque échange crée deux nouveaux arbres. La recherche exhaustive des voisins les plus proches possibles pour chaque ensemble possible de sous-arbres est le moyen le plus lent mais le plus optimisant d'effectuer cette recherche. Une recherche alternative plus étendue, l' élagage et la greffe de sous-arbre (SPR), sélectionne et supprime un sous-arbre de l'arbre principal et le réinsère ailleurs dans l'arbre principal pour créer un nouveau nœud. Enfin, la bissection et reconnexion d'arbres (TBR) détache un sous-arbre de l'arbre principal au niveau d'un nœud intérieur puis tente toutes les connexions possibles entre les arêtes des deux arbres ainsi créés. La complexité croissante de la technique de réarrangement arborescent est en corrélation avec l'augmentation du temps de calcul requis pour la recherche, mais pas nécessairement avec leurs performances.

Le SPR peut être divisé en uSPR : Unrooted SPR, rSPR : Rooted SPR. uSPR est appliqué aux arbres non racinés et se déroule comme suit : cassez n'importe quel bord. Joignez une extrémité de l'arête (sélectionnée arbitrairement) à n'importe quelle autre arête de l'arborescence. rSPR est appliqué aux arbres enracinés*, et va : briser n'importe quel bord sauf le bord menant au nœud racine. Joignez une extrémité du bord (plus précisément : l'extrémité du bord qui est la PLUS ÉLOIGNÉE de la racine) et attachez-la à n'importe quel autre bord de l'arbre.

* Dans cet exemple, la racine de l'arbre est marquée par un nœud de degré un, ce qui signifie que tous les nœuds de l'arbre ont soit le degré 1 soit le degré 3. Une approche alternative, utilisée dans Bordewich et Semple, consiste à considérer le nœud racine comme ont le degré 2, et d'avoir une règle spéciale pour rSPR.

Le nombre de déplacements SPR ou TBR nécessaires pour passer d'un arbre à un autre peut être calculé en produisant une forêt d'accord maximum comprenant (respectivement) des arbres enracinés ou non. Ce problème est NP difficile mais à paramètre fixe traitable.

Fusion d'arbres

Le type le plus simple de fusion d'arbres commence avec deux arbres déjà identifiés comme quasi-optimaux ; ainsi, ils ont très probablement la majorité de leurs nœuds corrects mais peuvent ne pas résoudre correctement les "feuilles" d'arbres individuels ; par exemple, la séparation ((A,B),(C,D)) à l'extrémité d'une branche par rapport à ((A,C),(B,D)) peut ne pas être résolue. La fusion d'arbres échange ces deux solutions entre deux arbres par ailleurs presque optimaux. Des variantes de la méthode utilisent des algorithmes génétiques standard avec une fonction objectif définie pour échanger des sous-arbres à haut score en arbres principaux qui sont globalement à haut score.

Recherche sectorielle

Une stratégie alternative consiste à détacher une partie de l'arbre (qui peut être sélectionné au hasard, ou en utilisant une approche plus stratégique) et d'effectuer TBR/SPR/NNI sur ce sous-arbre. Ce sous-arbre optimisé peut ensuite être remplacé sur l'arbre principal, améliorant, espérons-le, le p-score.

Arbre à la dérive

Pour éviter le piégeage dans les optima locaux, une approche de « recuit simulé » peut être utilisée, dans laquelle l'algorithme est parfois autorisé à traiter des arbres candidats sous-optimaux, avec une probabilité liée à leur distance par rapport à l'optimum.

Fusion d'arbres

Une fois qu'une gamme d'arbres également optimale a été rassemblée, il est souvent possible de trouver un meilleur arbre en combinant les « bons morceaux » d'arbres séparés. Des sous-groupes avec une composition identique mais une topologie différente peuvent être commutés et les arbres résultants évalués.

Les références

  1. ^ un b Felsenstein J. (2004). Inférer la phylogénie Sinauer Associates : Sunderland, MA.
  2. ^ Takahashi K, Nei M. (2000). Efficacité des algorithmes rapides d'inférence phylogénétique sous les critères de parcimonie maximale, d'évolution minimale et de vraisemblance maximale lorsqu'un grand nombre de séquences est utilisé. Mol Biol Evol 17(8) : 1251-8.
  3. ^ Bordewich M, Semple C. 2005. Sur la complexité de calcul du sous-arbre enraciné et de la distance de regreffe Ann. Peigne. 8:409-23
  4. ^ WHIDDEN, C., BEIKO, RG et ZEH, N. 2016. Algorithmes à paramètres fixes et d'approximation pour les forêts d'accord maximald'arbres multifurquants. Algorithmica, 74, 1019-1054
  5. ^ CHEN, J., FAN, J.-H. et SZE, S.-H. 2015. Algorithmes paramétrés et d'approximation pour la forêt d'accord maximum dans les arbres multifurquants. Informatique théorique, 562, 496-512.
  6. ^ Matsuda H. (1996). Inférence phylogénétique des protéines utilisant le maximum de vraisemblance avec un algorithme génétique. Symposium du Pacifique sur la bioinformatique 1996 , pp512-23.
  7. ^ A b c Goloboff, P. (1999). Analyser de grands ensembles de données dans des délais raisonnables : solutions pour Composite Optima. Cladistique, 15(4), 415–428. doi : 10.1006/clad.1999.0122