Institute of Theoretical Computer Science, Ulm University, 89069 Ulm, Germany.
BMC Bioinformatics. 2010 Jan 18;11 Suppl 1(Suppl 1):S27. doi: 10.1186/1471-2105-11-S1-S27.
Finding sequences of evolutionary operations that transform one genome into another is a classical problem in comparative genomics. While most of the genome rearrangement algorithms assume that there is exactly one copy of each gene in both genomes, this does not reflect the biological reality very well - most of the studied genomes contain duplicated gene content, which has to be removed before applying those algorithms. However, dealing with unequal gene content is a very challenging task, and only few algorithms allow operations like duplications and deletions, especially if the duplicated or deleted segments are of arbitrary size.
We recently proposed a heuristic algorithm for sorting unichromosomal genomes by reversals, block interchanges, tandem duplications, and deletions. In this paper, we extend this approach to multichromosomal genomes. We are now able to sort a multichromosomal ancestral genome into a genome of a descendant by a large set of different operations, including tandem duplications and deletions of segments of arbitrary size.
Experimental results show that our algorithm finds sorting sequences that have a weight close to the true evolutionary distance.
寻找将一个基因组转化为另一个基因组的进化操作序列是比较基因组学中的一个经典问题。虽然大多数基因组重排算法都假设两个基因组中每个基因只有一个拷贝，但这并不能很好地反映生物学现实——大多数研究的基因组都包含重复的基因内容，在应用这些算法之前必须将其去除。然而，处理不等基因含量是一项极具挑战性的任务，只有少数算法允许进行重复和删除等操作，特别是如果重复或删除的片段大小任意。
我们最近提出了一种通过反转、块交换、串联重复和删除来对单染色体基因组进行排序的启发式算法。在本文中，我们将这种方法扩展到多染色体基因组。我们现在能够通过一大组不同的操作，包括任意大小片段的串联重复和删除，将多染色体祖先基因组排序为后代基因组。
实验结果表明，我们的算法找到了接近真实进化距离的排序序列。
