A Median Solver and Phylogenetic Inference Based on Double-Cut-and-Join Sorting

Journal of computational biology: A journal of computational molecular cell biology

YuLin^3¹  BingFeng^2²  JunZhou^2³  RuofanXia^1,2⁴ 

[1] Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina^2;Institute of Computational Biology, Tianjin University, Tianjin, China^4;Research School of Computer Science, Australian National University, Canberra, Australia^3;School of Computer Science and Technology, Tianjin University, Tianjin, China^1

关键词: big phylogeny problem;    median problem;    phylogenetic inference;    simulated annealing;    small phylogeny problem;   

DOI  :  10.1089/cmb.2017.0157

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

Genome rearrangement is known as one of the main evolutionary mechanisms on the genomic level. Phylogenetic analysis based on rearrangement played a crucial role in biological research in the past decades, especially with the increasing availability of fully sequenced genomes. In general, phylogenetic analysis aims to solve two problems: small parsimony problem (SPP) and big parsimony problem (BPP). Maximum parsimony is a popular approach for SPP and BPP, which relies on iteratively solving an NP-hard problem, the median problem. As a result, current median solvers and phylogenetic inference methods based on the median problem all face serious problems on scalability and cannot be applied to data sets with large and distant genomes. In this article, we propose a new median solver for gene order data that combines double-cut-and-join sorting with the simulated annealing algorithm. Based on this median solver, we built a new phylogenetic inference method to solve both SPP and BPP problems. Our experimental results show that the new median solver achieves an excellent performance on simulated data sets, and the phylogenetic inference tool built based on the new median solver has a better performance than other existing methods.

【 授权许可】

Unknown