A Median Solver and Phylogenetic Inference Based on DCJ Sorting

摘要

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 tries 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 a 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 datasets with large and distant genomes. In this paper, we propose a new median solver for gene order data that combines double-cut-and-join sorting with the Simulated Annealing algorithm (SAMedian). Based on the 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 presents an excellent performance on simulated datasets and the phylogenetic inference tool built based on the new median solver has a better performance than other existing methods.