Assignment of orthologous genes via genome rearrangement
Assignment of orthologous genes via genome rearrangement
复制标题
DOI：
10.1109/tcbb.2005.48
复制
发表时间：
2005-10-01
影响因子：
4.5
通讯作者：
Jiang, T
中科院分区：
文献类型：
--
作者：
Chen, X;Zheng, J;Jiang, T
在一对基因组之间定位同源基因是比较基因组学中的一个基本而又具有挑战性的问题。现有的方法，分配直系同源物的基础上的DNA或蛋白质序列之间的相似性，可能会作出错误的分配时，序列相似性不能清楚地描绘的进化关系之间的基因相同的家庭。在本文中，我们提出了一种新的方法来直系同源物分配，考虑到在基因组水平上的序列相似性和进化事件，其中直系同源基因被假定为对应于彼此在基因组重排下的最简约的进化方案。首先，该问题被公式化为计算两个感兴趣的基因组之间的重复的符号反转距离。然后，将问题分解为两个新的优化问题，称为最小公共划分和最大循环分解，并给出了有效的启发式算法。按照这种方法，我们已经实现了一个高通量系统分配直系同源基因的基因组规模，称为SOAR，并测试了模拟数据和真实的基因组序列数据。与最近完全基于同源性搜索的直系同源物分配方法（称为INPARANOID）相比，SOAR在真实的数据集上的灵敏度方面表现出略微更好的性能，因为它能够识别INPARANOID错过的几个正确的直系同源物对。仿真结果表明，SOAR，在一般情况下，执行更好的迭代样本算法在计算反转距离和分配正确的同源。
The assignment of orthologous genes between a pair of genomes is a fundamental and challenging problem in comparative genomics. Existing methods that assign orthologs based on the similarity between DNA or protein sequences may make erroneous assignments when sequence similarity does not clearly delineate the evolutionary relationship among genes of the same families. In this paper, we present a new approach to ortholog assignment that takes into account both sequence similarity and evolutionary events at a genome level, where orthologous genes are assumed to correspond to each other in the most parsimonious evolving scenario under genome rearrangement. First, the problem is formulated as that of computing the signed reversal distance with duplicates between the two genomes of interest. Then, the problem is decomposed into two new optimization problems, called minimum common partition and maximum cycle decomposition, for which efficient heuristic algorithms are given. Following this approach, we have implemented a high-throughput system for assigning orthologs on a genome scale, called SOAR, and tested it on both simulated data and real genome sequence data. Compared to a recent ortholog assignment method based entirely on homology search (called INPARANOID), SOAR shows a marginally better performance in terms of sensitivity on the real data set because it is able to identify several correct orthologous pairs that are missed by INPARANOID. The simulation results demonstrate that SOAR, in general, performs better than the iterated exemplar algorithm in terms of computing the reversal distance and assigning correct orthologs.