Persistent Phylogeny

Character-based parsimony models have been among the most studied notions in computational evolution, with a special focus on the perfect phylogeny model, where each character can be acquired at most once and cannot be lost. Soon this model has been touted as unrealistic,.

On the other hand this model has been popular in Bioinformatics, as several efficient algorithms have been proposed. This project studies a generalization of the perfect phylogeny model, called persistent phylogeny, where each character can be acquired at most once and lost at most once in the entire tree. The main computational problem is, given a binary matrix M, to compute a tree (if it exists) explaining M.

We have proposed a fixed-parameter algorithm for thist problem and for a more general version where some species are known to never have acquired a certain character in this evolution.

pp-9pp-12

Software

Polynomial-time implementation is available on github, where you can also find support.

Exponential-time implementation is available on github, where you can also find support.

References

Bonizzoni, P., Della Vedova, G., & Trucco, G. (2016). Solving the Persistent Phylogeny Problem in polynomial time. Arxiv

Bonizzoni, P., Carrieri, A.P., Della Vedova, G., Rizzi R. & Trucco, G. (2016). A colored graph approach to perfect phylogeny with persistent characters. Theoretical Computer Science.

Bonizzoni, P., Carrieri, A.P., Della Vedova, G., & Trucco, G. (2014). Explaining evolution via constrained persistent perfect phylogeny. BMC GENOMICS, 15(Suppl 6), S10.

Bonizzoni, P., Carrieri, A.P., Della Vedova, G., Dondi, R., & Przytycka, T. (2014). When and How the Perfect Phylogeny Model Explains Evolution. In N. Jonoska, & M. Saito (editors, Discrete and Topological Models in Molecular Biology (pp. 67-83). Springer.

Bonizzoni, P., Braghin, C., Dondi, R., & Trucco, G. (2012). The binary perfect phylogeny with persistent characters. THEORETICAL COMPUTER SCIENCE, 454, 51-63. Arxiv