Achieving large and distant ancestral genome inference by using an improved discrete quantum-behaved particle swarm opti
- PDF / 2,615,716 Bytes
- 30 Pages / 595.276 x 790.866 pts Page_size
- 55 Downloads / 139 Views
RESEARCH ARTICLE
Open Access
Achieving large and distant ancestral genome inference by using an improved discrete quantum‑behaved particle swarm optimization algorithm Zhaojuan Zhang1, Wanliang Wang1* , Ruofan Xia2, Gaofeng Pan2†, Jiandong Wang2† and Jijun Tang2,3 *Correspondence: [email protected] † Gaofeng Pan and Jiandong Wang contributed equally to this work 1 College of Computer Science and Technology, Zhejiang University of Technology, Liuhe Road, Hangzhou, China Full list of author information is available at the end of the article
Abstract Background: Reconstructing ancestral genomes is one of the central problems presented in genome rearrangement analysis since finding the most likely true ancestor is of significant importance in phylogenetic reconstruction. Large scale genome rearrangements can provide essential insights into evolutionary processes. However, when the genomes are large and distant, classical median solvers have failed to adequately address these challenges due to the exponential increase of the search space. Consequently, solving ancestral genome inference problems constitutes a task of paramount importance that continues to challenge the current methods used in this area, whose difficulty is further increased by the ongoing rapid accumulation of whole-genome data. Results: In response to these challenges, we provide two contributions for ancestral genome inference. First, an improved discrete quantum-behaved particle swarm optimization algorithm (IDQPSO) by averaging two of the fitness values is proposed to address the discrete search space. Second, we incorporate DCJ sorting into the IDQPSO (IDQPSO-Median). In comparison with the other methods, when the genomes are large and distant, IDQPSO-Median has the lowest median score, the highest adjacency accuracy, and the closest distance to the true ancestor. In addition, we have integrated our IDQPSO-Median approach with the GRAPPA framework. Our experiments show that this new phylogenetic method is very accurate and effective by using IDQPSO-Median. Conclusions: Our experimental results demonstrate the advantages of IDQPSOMedian approach over the other methods when the genomes are large and distant. When our experimental results are evaluated in a comprehensive manner, it is clear that the IDQPSO-Median approach we propose achieves better scalability compared to existing algorithms. Moreover, our experimental results by using simulated and real datasets confirm that the IDQPSO-Median, when integrated with the GRAPPA framework, outperforms other heuristics in terms of accuracy, while also continuing to infer phylogenies that were equivalent or close to the true trees within 5 days of computation, which is far beyond the difficulty level that can be handled by GRAPPA.
© The Author(s) 2020. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original au
Data Loading...
