Groupe d’études et de recherche en analyse des décisions

G-96-59

BIONJ: une version améliorée de l'algorithme NJ basée sur un modèle simple des données biologiques

L'algorithme NJ de Saitou et Nei (1987) est l'une des méthodes les plus utilisées pour reconstruire des phylogénies à partir de matrices de distances évolutives. Il suit un schéma agglomératif qui consiste à choisir une paire de taxons, créer un nouveau noeud qui les représente, réduire la matrice de distances en remplaçant les deux taxons par ce noeud, et itérer jusqu'à ce qu'il ne reste plus que trois taxons. Cet article propose une amélioration de NJ qui est essentiellement destinée à traiter de distances issues de séquences alignées. Ce nouvel algorithme, BIONJ, repose sur un modèle au premier ordre des variances et covariances des distances évolutives estimées. A chaque étape, ce modèle permet de choisir au sein d'une famille de formules de réduction admissibles, celle qui minimise la variance de la nouvelle matrice de distance. En procédant ainsi, on dispose de meilleurs estimateurs pour choisir les paires de taxons à agglomérer et, par comparaison avec NJ, ces estimateurs sont de meilleurs en meilleurs au fur et à mesure de l'avancement de l'algorithme. BIONJ conserve les bonnes propriétés de NJ et en particulier son temps calcul réduit. Pour juger de son efficacité, nous avons effectué de nombreuses simulations sur des arbres modèles issus de Kumar (1996) et sur des arbres aléatoires en suivant un schéma proposé par Kuhner et Felsenstein (1994). Les résultats montrent que BIONJ et NJ ont des résultats proches lorsque les taux de substitutions sont très faibles (égal ou inférieur à 0.1). Avec des taux plus élevés, une amélioration très significative de la capacité de prédiction topologique est obtenue par BIONJ. Par exemple avec 12 taxons, le gain relatif est en moyenne de 12% environ pour les conditions d'évolution testées. Lorsque l'arbre modèle s'écarte nettement de l'hypothèse de l'horloge moléculaire, des gains plus importants peuvent être attendus, e.g., approximativement 35% pour un arbre de 12 taxons issu de (Kumar 1996) et pour des taux de substitution élevés (égal ou inférieur à 1).

, 24 pages