Phylogenetic Analysis with Complex Genome Rearrangement Events

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

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.