TY - GEN
T1 - Fast computation of the exact hybridization number of two phylogenetic trees
AU - Wu, Yufeng
AU - Wang, Jiayin
PY - 2010
Y1 - 2010
N2 - Hybridization is a reticulate evolutionary process. An established problem on hybridization is computing the minimum number of hybridization events, called the hybridization number, needed in the evolutionary history of two phylogenetic trees. This problem is known to be NP-hard. In this paper, we present a new practical method to compute the exact hybridization number. Our approach is based on an integer linear programming formulation. Simulation results on biological and simulated datasets show that our method (as implemented in program SPRDist) is more efficient and robust than an existing method.
AB - Hybridization is a reticulate evolutionary process. An established problem on hybridization is computing the minimum number of hybridization events, called the hybridization number, needed in the evolutionary history of two phylogenetic trees. This problem is known to be NP-hard. In this paper, we present a new practical method to compute the exact hybridization number. Our approach is based on an integer linear programming formulation. Simulation results on biological and simulated datasets show that our method (as implemented in program SPRDist) is more efficient and robust than an existing method.
UR - https://www.scopus.com/pages/publications/77953759624
U2 - 10.1007/978-3-642-13078-6_23
DO - 10.1007/978-3-642-13078-6_23
M3 - 会议稿件
AN - SCOPUS:77953759624
SN - 3642130771
SN - 9783642130779
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 203
EP - 214
BT - Bioinformatics Research and Applications - 6th International Symposium, ISBRA 2010, Proceedings
T2 - 6th International Symposium on Bioinformatics Research and Applications, ISBRA 2010
Y2 - 23 May 2010 through 26 May 2010
ER -