Species-Driven Persistent Phylogeny

• Autorzy: Bonizzoni, P. , Carrieri, A. P. , Della Vedova, G. , Rizzi, R. , Trucco, G.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

perfect phylogeny; persistent perfect phylogeny; galled tree

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 47--63
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Bonizzoni, P.

• DISCo, Università degli Studi di Milano-Bicocca, Italy,

autor

Carrieri, A. P.

• IBM Research, UK,

autor

Della Vedova, G.

• DISCo, Università degli Studi di Milano-Bicocca, Italy,

autor

Rizzi, R.

• DISCo, Università degli Studi di Milano-Bicocca, Italy,

autor

Trucco, G.

• Dipartimento di Informatica, Università degli Studi di Milano, Italy,

Bibliografia

• [1] Gusfield D. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997.
• [2] Rens KEv, Mäkinen V, Tomescu AI. SNV-PPILP: refined SNV calling for tumor data using perfect phylogenies and ILP. Bioinformatics, 2015;31(7):1133–1135. doi:10.1093/bioinformatics/btu755.
• [3] Hajirasouliha I, Mahmoody A, Raphael BJ. A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data. Bioinformatics, 2014;30(12):i78–i86. doi:10.1093/bioinformatics/btu284.
• [4] El-Kebir M, Oesper L, Acheson-Field H, Raphael BJ. Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics, 2015;31(12):i62–i70. doi:10.1093/bioinformatics/btv261.
• [5] El-Kebir M, Satas G, Oesper L, Raphael BJ. Inferring the Mutational History of a Tumor Using Multistate Perfect Phylogeny Mixtures. Cell Systems, 2016;3(1):43–53. doi:http://dx.doi.org/10.1016/j.cels. 2016.07.004.
• [6] Gusfield D. Efficient algorithms for inferring evolutionary trees. Networks, 1991. pp. 19–28.
• [7] Pe’er I, Pupko T, Shamir R, Sharan R. Incomplete Directed Perfect Phylogeny. SIAM Journal on Computing, 2004;33(3):590–607. doi:10.1137/s0097539702406510. URL http://dx.doi.org/10.1137/S0097539702406510.
• [8] Bonizzoni P, Della Vedova G, Dondi R, Li J. The haplotyping problem: a view of computational models and solutions. International Journal of Computer and Science Technology, 2003;18:675–688. doi:10.1007/BF02945456.
• [9] Gusfield D. Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In: Proc. 6th Annual Conference on Research in Computational Molecular Biology (RECOMB 2002). 2002 pp. 166–175. doi:10.1145/565196.565218.
• [10] Bafna V, Gusfield D, Lancia G, Yooseph S. Haplotyping as perfect phylogeny: A direct approach. Journal of Computational Biology, 2003;10(3-4):323–340. doi: 10.1089/10665270360688048.
• [11] Bonizzoni P. A linear time algorithm for the Perfect Phylogeny Haplotype problem. Algorithmica, 2007;48(3):267–285. doi:10.1007/s00453-007-0094-3.
• [12] Ding Z, Filkov V, Gusfield D. A Linear Time algorithm for Perfect Phylogeny Haplotyping (PPH) problem. Journal of Computational Biology, 2006;13(2):522–553. doi:10.1089/cmb.2006.13.522.
• [13] Felsenstein J. Inferring Phylogenies. Sinauer Associates, Sunderland, MA (USA), 2004. ISBN-10:0878931775, 13:978-0878931774.
• [14] Fernández-Baca D, Lagergren J. A Polynomial-Time Algorithm for Near-Perfect Phylogeny. SIAM J. Comput., 2003;32(5):1115–1127. URL https://doi.org/10.1137/S0097539799350839.
• [15] Przytycka T, Davis G, Song N, Durand D. Graph Theoretical Insights into Dollo Parsimony and Evolution of Multidomain Proteins. Journal of Computational Biology, 2006;13(2):351–363. doi:10.1089/cmb.2006.13.351.
• [16] Maňuch J, Patterson M, Gupta A. Towards a Characterisation of the Generalised Cladistic Character Compatibility Problem for Non-branching Character Trees. In: ISBRA. 2011 pp. 440–451. doi:10.1007/978-3-642-21260-4_41.
• [17] Maňuch J, Patterson M, Gupta A. On the generalised character compatibility problem for non-branching character trees. In: Computing and Combinatorics. 2009 pp. 268–276. doi:10.1007/978-3-642-02882-3_27.
• [18] Bonizzoni P, Braghin C, Dondi R, Trucco G. The binary perfect phylogeny with persistent characters. Theoretical computer science, 2012;454:51–63. URL https://doi.org/10.1016/j.tcs.2012.05.035.
• [19] Bonizzoni P, Carrieri AP, Della Vedova G, Rizzi R, Trucco G. A colored graph approach to perfect phylogeny with persistent characters. Theoretical Computer Science, 2017;658:60–73. doi:10.1016/j.tcs.2016.08.015.
• [20] Gusfield D. Persistent phylogeny: a galled-tree and integer linear programming approach. In: Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics. ACM, 2015 pp. 443–451.
• [21] Bonizzoni P, Carrieri AP, Della Vedova G, Trucco G. Explaining evolution via constrained persistent perfect phylogeny. BMC Genomics, 2014;15(Suppl 6):S10. doi:10.1186/1471-2164-15-S6-S10.
• [22] Griffiths RC, Marjoram P. Ancestral inference from samples of DNA sequences with recombination. Journal of Computational Biology, 1996;3(4):479–502. doi:: 10.1089/cmb.1996.3.479.
• [23] Wang L, Zhang K, Zhang L. Perfect phylogenetic networks with recombination. Journal of Computational Biology, 2001;8(1):69–78. doi:10.1089/106652701300099119.
• [24] Gusfield D, Eddhu S, Langley C. Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. Journal of Bioinformatics and Computational Biology, 2004;02(1):173–213. doi: 10.1142/S0219720004000521.
• [25] Zheng J, Rogozin IB, Koonin EV, Przytycka TM. Support for the Coelomata Clade of Animals from a Rigorous Analysis of the Pattern of Intron Conservation. Mol. Biol. Evol., 2007;24(11):2583–2592. URL https://doi.org/10.1093/molbev/msm207.
• [26] Bonizzoni P, Carrieri AP, Della Vedova G, Dondi R, Przytycka TM. When and How the Perfect Phylogeny Model Explains Evolution. In: Jonoska N, Saito M (eds.), Discrete and Topological Models in Molecular Biology, Natural Computing Series, pp. 67–83. Springer Berlin Heidelberg, Berlin, Germany, 2014. doi:10.1007/978-3-642-40193-0_4.
• [27] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. MIT Press, 2nd edition, 2001. ISBN-0262032937, 9780262032933.

Identyfikatory

DOI

10.3233/FI-2017-1552