Faculty of Medicine, Heinrich Heine University, Düsseldorf, Germany.
Department of Mathematic, Simon Fraser University, Canada.
J Bioinform Comput Biol. 2021 Dec;19(6):2140009. doi: 10.1142/S0219720021400096. Epub 2021 Nov 19.
The Small Parsimony Problem (SPP) aims at finding the gene orders at internal nodes of a given phylogenetic tree such that the overall genome rearrangement distance along the tree branches is minimized. This problem is intractable in most genome rearrangement models, especially when gene duplication and loss are considered. In this work, we describe an Integer Linear Program algorithm to solve the SPP for natural genomes, i.e. genomes that contain conserved, unique, and duplicated markers. The evolutionary model that we consider is the DCJ-indel model that includes the Double-Cut and Join rearrangement operation and the insertion and deletion of genome segments. We evaluate our algorithm on simulated data and show that it is able to reconstruct very efficiently and accurately ancestral gene orders in a very comprehensive evolutionary model.
简约性问题（SPP）旨在找到给定系统发育树内部节点的基因顺序，以使沿树分支的整体基因组重排距离最小化。在大多数基因组重排模型中，特别是在考虑基因复制和缺失时，这个问题是难以解决的。在这项工作中，我们描述了一种整数线性规划算法，用于解决自然基因组的 SPP 问题，即包含保守、独特和复制标记的基因组。我们考虑的进化模型是 DCJ-插入缺失模型，它包括双切割和连接重排操作以及基因组片段的插入和缺失。我们在模拟数据上评估了我们的算法，并表明它能够在非常全面的进化模型中非常有效地和准确地重建祖先基因顺序。
