The perfect phylogeny is a widely used model in phylogenetics, since it provides an effective representation of evolution of binary characters in several contexts, such as for example in haplotype inference. The model, which is conceptually the simplest among those actually used, is based on the infinite sites assumption, that is no character can mutate more than once in the whole tree. Since a large number of biological phenomena cannot be modeled by the perfect phylogeny, it becomes important to find generalizations that retain the computational tractability of the original model, but are more flexible in modeling biological data when the infinite site assumption is violated, e.g. because of back mutations. In this paper, we introduce a new model—called species-driven persistent phylogeny—and we study the relations between three different formulations: perfect phylogeny, persistent phylogeny, galled trees, and species-driven persistent phylogeny. The species-driven persistent phylogeny model is intermediate between the perfect and the persistent phylogeny, since a perfect phylogeny allows no back mutations and a persistent phylogeny allows each character to back mutate only once. We describe an algorithm to compute a species-driven persistent phylogeny and we prove that every matrix admitting a galled-tree also admits a species-driven persistent phylogeny.

Species-driven persistent phylogeny / P. Bonizzoni, A.P. Carrieri, G. Della Vedova, R. Rizzi, G. Trucco. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 154:1-4(2017 Sep), pp. 47-63. [10.3233/FI-2017-1552]

Species-driven persistent phylogeny

G. Trucco
2017

Abstract

The perfect phylogeny is a widely used model in phylogenetics, since it provides an effective representation of evolution of binary characters in several contexts, such as for example in haplotype inference. The model, which is conceptually the simplest among those actually used, is based on the infinite sites assumption, that is no character can mutate more than once in the whole tree. Since a large number of biological phenomena cannot be modeled by the perfect phylogeny, it becomes important to find generalizations that retain the computational tractability of the original model, but are more flexible in modeling biological data when the infinite site assumption is violated, e.g. because of back mutations. In this paper, we introduce a new model—called species-driven persistent phylogeny—and we study the relations between three different formulations: perfect phylogeny, persistent phylogeny, galled trees, and species-driven persistent phylogeny. The species-driven persistent phylogeny model is intermediate between the perfect and the persistent phylogeny, since a perfect phylogeny allows no back mutations and a persistent phylogeny allows each character to back mutate only once. We describe an algorithm to compute a species-driven persistent phylogeny and we prove that every matrix admitting a galled-tree also admits a species-driven persistent phylogeny.
perfect phylogeny; persistent perfect phylogeny; galled-tree
Settore INF/01 - Informatica
   Automi e Linguaggi Formali: Aspetti Matematici e Applicativi
   MINISTERO DELL'ISTRUZIONE E DEL MERITO
   2010LYA9RH_005
set-2017
Article (author)
File in questo prodotto:
File Dimensione Formato  
fi_2017_154-1-4_fi-154-1-4-fi1552_fi-154-fi1552.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 166.75 kB
Formato Adobe PDF
166.75 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/523282
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact