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

直向同源基因（orthologs）是不同物种中的基因，它们直接从一个共同的祖先基因进化而来。直向同源基因的基因组规模分配是计算生物学中的一个基本和具有挑战性的问题，在比较基因组学和功能基因组学中有着广泛的应用。本项目继续发展了用于在密切相关的基因组之间分配直系同源物的简约方法，该方法基本上试图将一个基因组转化为另一种是由最小数量的基因组重组事件引起的，包括逆转、易位、融合和裂变，以及基因复制事件。该项目解决了三个关键的算法问题，包括（i）有符号的逆转距离与重复，（ii）有符号的换位距离与重复，和（iii）最小公共字符串划分。有效的解决方案，这些问题的每一个相结合，并纳入一个软件系统的直系同源物分配，称为MSOAR。 该项目包括全基因组分析的orthopathy（和旁系同源）的关系，以验证该方法，更重要的是，解决几个重要的进化生物学问题，包括表征两个基因组中重复基因的获得和损失，阐明一个基因组相对于另一个基因组的基因运动，和基因复制的不同机制的量化。智力价值。简约的方法提出了一种新的方法来执行基因组-考虑到基因序列和位置的宽直系同源物分配。上述算法问题在文献中是新的，它们的解决方案需要引入新颖的算法设计和分析技术。关于模式物种中基因复制和复制机制的量化问题在进化生物学中具有根本的重要性。影响更广泛。由于直系同源物分配是比较基因组学中的一个基本问题，并已成为基因组学几乎所有领域的常规实践，因此MSOAR将在生物学和基因组学中发现广泛的应用。此外，该研究将为两名计算机科学研究生提供计算生物学跨学科领域的培训机会。2有关该NSF项目的信息将在以下网站上提供：http://msoar.cs.ucr.edu/

Orthologous genes, or orthologs, are genes in different speciesthat have evolved directly from a common ancestral gene.Genome-scale assignment of orthologs is a fundamental andchallenging problem in computational biology, and has a wide rangeof applications in comparative genomics and functional genomics.This project continues the development of the parsimony approachfor assigning orthologs between closely related genomes which essentially attempts to transform one genome into another by the smallest number of genome rearrangementevents including reversal, translocation, fusion, and fission, as well asgene duplication events. The project addresses three key algorithmicproblems including (i) signed reversal distance withduplicates, (ii) signed transposition distance with duplicates,and (iii) minimum common string partition. Efficient solutions to each ofthese 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-wideortholog assignment that takes into account both gene sequences and locations.The above algorithmic problems are new in the literature and their solutionslikely require the introduction of novel algorithm design and analysistechniques. 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 andhas become a routine practice in almost all areas of genomics, MSOARwill 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/