Computational Complexity of Inferring Phylogenies by Compatibility

Abstract

A well-known approach to inferring phylogenies involves finding a phylogeny with the largest number of characters that are perfectly compatible with it. Variations of this problem depend on whether characters are: cladistic (rooted) or qualitative (unrooted); binary (two states) or unconstrained (more than one state). The computational cost of known algorithms that guarantee solutions to these problems increases at least exponentially with problem size; practical computational considerations restrict the use of such algorithms to analyzing problems of small size. We establish that the four basic variants of the compatibility problem are all NPcomplete and, thus, are so difficult computationally that for them efficient optimal algorithms are not likely to exist Une approche bien connue a l'etude de revolution des especes est basee sur la recherche de l'arbre phylogenetique avec lequel il y a un nombre maximal de caracteres compatibles. Des variantes de ce probleme impliquent des caracteres soit cladistiques (avec racine), soit qualitatifs (sans racine); des caracteres soit binaires (deux valeurs), soit sans contrainte (plus qu'une valeur). Les algorithmes connus pour resoudre ces problemes exigent un temps d'ordinateur qui augmente de facon exponentielle en fonction de la taille du probleme; ainsi, a toute fin pratique, on est contraint a des petits problemes. Nous demontrons que les quatre variantes du probleme de compatibility sont toutes NP-completes, done il est presque certain qu'ils sont trop difficiles pour que des algorithmes efficaces puissent exister.