Live phylogeny with polytomies: Finding the most compact parsimonious trees.
Comput Biol Chem
; 69: 171-177, 2017 08.
Article
in En
| MEDLINE
| ID: mdl-28391977
ABSTRACT
Construction of phylogenetic trees has traditionally focused on binary trees where all species appear on leaves, a problem for which numerous efficient solutions have been developed. Certain application domains though, such as viral evolution and transmission, paleontology, linguistics, and phylogenetic stemmatics, often require phylogeny inference that involves placing input species on ancestral tree nodes (live phylogeny), and polytomies. These requirements, despite their prevalence, lead to computationally harder algorithmic solutions and have been sparsely examined in the literature to date. In this article we prove some unique properties of most parsimonious live phylogenetic trees with polytomies, and their mapping to traditional binary phylogenetic trees. We show that our problem reduces to finding the most compact parsimonious tree for n species, and describe a novel efficient algorithm to find such trees without resorting to exhaustive enumeration of all possible tree topologies.
Key words
Full text:
1
Collection:
01-internacional
Database:
MEDLINE
Main subject:
Phylogeny
/
Algorithms
Type of study:
Diagnostic_studies
/
Risk_factors_studies
Language:
En
Journal:
Comput Biol Chem
Year:
2017
Document type:
Article