TY - GEN
T1 - Using INC Within Divide-and-Conquer Phylogeny Estimation
AU - Le, Thien
AU - Sy, Aaron
AU - Molloy, Erin K.
AU - Zhang, Qiuyi (Richard)
AU - Rao, Satish
AU - Warnow, Tandy
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - In a recent paper (Zhang, Rao, and Warnow, Algorithms for Molecular Biology 2019), the INC (incremental tree building) algorithm was presented and proven to be absolute fast converging under standard sequence evolution models. A variant of INC which allows a set of disjoint constraint trees to be provided and then uses INC to merge the constraint trees was also presented (i.e., Constrained INC). We report on a study evaluating INC on a range of simulated datasets, and show that it has very poor accuracy in comparison to standard methods. We also explore the design space for divide-and-conquer strategies for phylogeny estimation that use Constrained INC, and show modifications that provide improved accuracy. In particular, we present INC-ML, a divide-and-conquer approach to maximum likelihood (ML) estimation that comes close to the leading ML heuristics in terms of accuracy, and is more accurate than the current best distance-based methods.
AB - In a recent paper (Zhang, Rao, and Warnow, Algorithms for Molecular Biology 2019), the INC (incremental tree building) algorithm was presented and proven to be absolute fast converging under standard sequence evolution models. A variant of INC which allows a set of disjoint constraint trees to be provided and then uses INC to merge the constraint trees was also presented (i.e., Constrained INC). We report on a study evaluating INC on a range of simulated datasets, and show that it has very poor accuracy in comparison to standard methods. We also explore the design space for divide-and-conquer strategies for phylogeny estimation that use Constrained INC, and show modifications that provide improved accuracy. In particular, we present INC-ML, a divide-and-conquer approach to maximum likelihood (ML) estimation that comes close to the leading ML heuristics in terms of accuracy, and is more accurate than the current best distance-based methods.
KW - Divide-and-conquer
KW - Inferring the evolutionary phylogeny of species
KW - Maximum likelihood
KW - Phylogeny estimation
KW - Sample complexity
UR - http://www.scopus.com/inward/record.url?scp=85066130811&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85066130811&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-18174-1_12
DO - 10.1007/978-3-030-18174-1_12
M3 - Conference contribution
AN - SCOPUS:85066130811
SN - 9783030181734
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 167
EP - 178
BT - Algorithms for Computational Biology - 6th International Conference, AlCoB 2019, Proceedings
A2 - Martín-Vide, Carlos
A2 - Holmes, Ian
A2 - Vega-Rodríguez, Miguel A.
PB - Springer
T2 - 6th International Conference on Algorithms for Computational Biology, AlCoB 2019
Y2 - 28 May 2019 through 30 May 2019
ER -