III-CXT: Collaborative Research: A High-Throughput Approach to the Assignment of Orthologous Genes Based on Genome Rearrangement

同源基因，或称同源基因，是指不同物种中直接由共同祖先基因进化而来的基因。同源基因的基因组尺度定位是计算生物学中的一个基础性和挑战性问题，在比较基因组学和功能基因组学中有着广泛的应用。本项目继续发展在密切相关的基因组之间分配同源物的简约方法，该方法本质上试图通过最小数量的基因组重排事件（包括反转、易位、融合、裂变以及基因复制事件）将一个基因组转化为另一个基因组。该项目解决了三个关键的算法问题，包括(i)带有重复项的符号反转距离，（ii）带有重复项的符号换位距离，以及（iii）最小公共字符串划分。这些问题的有效解决方案被组合并纳入一个称为MSOAR的正交分配软件系统中。该项目包括对人类和小鼠基因组的同源（和旁系）关系的全基因组分析，以验证该方法，更重要的是，解决几个重要的进化生物学问题，包括两个基因组中复制基因的增益和损失的表征，一个基因组中相对于另一个基因组的基因运动的阐明，以及基因复制不同机制的量化。知识价值。该方法提出了一种新的方法来执行全基因组同源分配，同时考虑到基因序列和位置。上述算法问题在文献中是新的，它们的解决方案可能需要引入新的算法设计和分析技术。模式物种基因复制和复制机制的定量研究在进化生物学中具有重要意义。更广泛的影响。由于同源分配是比较基因组学的一个基本问题，并且已经成为基因组学几乎所有领域的常规实践，因此MSOAR将在生物学和基因组学中得到广泛的应用。此外，本研究将为两名计算机科学研究生提供在计算生物学交叉领域的训练机会。有关该NSF项目的信息将在网站http://msoar.cs.ucr.edu/上提供

Abstract Orthologous genes, or orthologs, are genes in different species that have evolved directly from a common ancestral gene. Genome-scale assignment of orthologs is a fundamental and challenging problem in computational biology, and has a wide range of applications in comparative genomics and functional genomics. This project continues the development of the parsimony approach for assigning orthologs between closely related genomes which essentially attempts to transform one genome into another by the smallest number of genome rearrangement events including reversal, translocation, fusion, and fission, as well as gene duplication events. The project addresses three key algorithmic problems including (i) signed reversal distance with duplicates, (ii) signed transposition distance with duplicates, and (iii) minimum common string partition. Efficient solutions to each of these problems are combined and incorporated into a software system for ortholog assignment, called MSOAR. The project encompasses genome-wide analysis of orthologous (and paralogous) relationships on the human and mouse genomes to valdiate the approach, and more importantly, to address several important evolutionary biological questions including the characterization of gains and losses of duplicated genes in the two genomes, the elucidation of gene movements in one genome with respect to the other genome, and the quantification of different mechanisms of gene duplication. Intellectual merit. The parsimony approach presents a novel method for performing genome-wide ortholog assignment that takes into account both gene sequences and locations. The above algorithmic problems are new in the literature and their solutions likely require the introduction of novel algorithm design and analysis techniques. The questions regarding gene duplication and quantification of the duplication mechanisms in model species are of fundamental importance in evolutionary biology. Broader impact. As ortholog assignment is a fundamental problem in comparative genomics and has become a routine practice in almost all areas of genomics, MSOAR will find itself a wide range of applications in biology and genomics. Moreover, the research will provide the training opportunity for two computer science graduate students in the interdisciplinary field of computational biology. Information concerning this NSF project will be provided at the website: http://msoar.cs.ucr.edu/