Phylogenetic Analysis with Complex Genome Rearrangement Events

描述(由申请人提供)：系统发育分析对广泛的生物和医学研究至关重要。在过去的几年里，一种基于全基因组中基因顺序和基因含量的新型数据吸引了越来越多的研究人员的兴趣。 具体目标：基因组进化的复杂性给数学模型和算法的开发者带来了许多令人兴奋的挑战。然而，目前的工具只能应用于通过非常简单的重排事件进化的小基因组(如细胞器基因组)，因此它们的使用范围有限。我们将通过以下几个方面解决这些问题：(1)复杂进化事件(如基因复制和丢失)的数学建模和理论分析；(2)系统发育和基因顺序重构的算法设计和实现；(3)通过在模拟和生物数据集上的广泛测试来评估这些新算法的性能；(4)使用算法工程技术和灵活的并行化方法实现算法。 贡献和更广泛的影响：拟议项目的更广泛的影响有几个。(1)基于复杂基因组重排的系统发育重建和祖先基因组推断的新理论和新算法的发展将极大地扩大该领域的研究范围，并在数学和计算生物学中引发有趣的新问题。(2)用于系统发育分析和基因组比较的高效和准确的软件，在大量真实数据集和广泛的模拟上进行测试，有望揭示新的进化模式，并使新的生物学问题的研究成为可能。(3)我们团队(或我们的合作者)托管的Web服务器将使生物学家能够通过用户友好的Web界面提交他们的数据集，并在合理的时间内返回结果，而不需要安装和学习并行计算的负担。(4)项目团队结合了数学建模、算法设计、高性能计算、比较基因组学和系统发育学方面的专业知识。该项目的学生(本科生和研究生)和博士后将获得宝贵的跨学科培训经验。(5)两所大学都建立了促进计算生物学研究的项目。该项目将使私人投资机构能够在两所大学的系之间建立密切的跨学科合作，并招募研究生(特别是少数族裔)进入这一快速增长的研究领域。

DESCRIPTION (provided by applicant): Phylogenetic analysis is crucial to a wide range of biological and medical research. A new type of data based on gene order and gene content within whole genomes has attracted increasing interest from researchers in the past several years. Specific Aims: The complexity of genome evolution poses many exciting challenges to developers of mathematical models and algorithms. However, the current tools can only be applied to small genomes (such as organelle genomes) evolving via very simple rearrangements events, hence their breadth of usage is limited. We will address these problems by: (1) mathematical modeling and theoretical analysis of complex evolutionary events such as gene duplication and loss; (2) algorithm design and implementation for phylogenetics and gene order reconstruction (3) performance assessment of these new algorithms through extensive testing on simulated and biological datasets; (4) high-performance implementation of the algorithms using algorithm engineering techniques and a flexible approach to parallelization. Contributions and Broader Impact: The broader impacts of the proposed project are several. (1) The development of new theories and algorithms for the efficient reconstruction of phylogenies and inference of ancestral genomes based on complex genome rearrangements will considerably enlarge the scope of research in the field and give rise to interesting new problems in mathematical and computational biology. (2) Efficient and accurate software for phylogenetic analysis and genome comparison, tested on a large variety of real datasets and on an extensive range of simulations, is expected to reveal new evolutionary patterns and to enable the investigation of novel biological questions. (3) A web server hosted by our group (or by our collaborators) will enable biologists to submit their datasets through a user-friendly web interface and get results back within reasonable amount of time, without the burden of installation and learning parallel computation. (4) The project team combines expertise in mathematic modeling, algorithm design, high-performance computing, comparative genomics, and phylogenetics. Students (both undergraduate and graduate) and postdocs on this project will receive valuable interdisciplinary training experience. (5) Both universities have established programs to boost research in computational biology. This project will enable the PIs to establish close interdisciplinary collaborations among departments from both universities and recruit graduate students (especially minorities) to this fast-growing research field.