ITR/AP(DEB): Collaborative Research `Computing Optimal Phylogenetic Trees under Genome Rearrangement Metrics'

该奖项为两名生物学家（Jansen和Boore）和三名计算机科学家（Moret，Warnow和Bader）之间的合作项目提供支持，以开发和测试新的算法和软件，用于从快速增加的基因组数据量中构建进化树。 估计遗传学对于一系列基础和应用生物学问题至关重要，例如艾滋病的流行病学，病毒因子的鉴定，蛋白质结构和功能的分析，RNA结构的预测;当然，它也是推断进化历史的基本工具。 用于重建同源性的方法最常应用于DNA序列。 在许多情况下，这些序列的变化率太低或太高，无法恢复准确的进化树。 一种新类型的数据，是在生物界迅速获得青睐的基因顺序和整个基因组中的内容，但到目前为止，很少有计算方法已经开发了这些类型的数据。 该项目的三个目标是：（1）开发从基因顺序和内容数据重建进化树的算法和软件;（2）通过在参数丰富的基因组进化模型下进行广泛的模拟研究并通过应用于真实的数据集，评估这些算法的性能;以及（3）使用算法工程技术和灵活的并行化方法，开发项目中设计的最佳算法的高性能实现。 该项目将在生物学方面作出重大贡献，方法是开发新的基因组进化模型，加深对叶绿体和线粒体基因组进化的了解;在计算机科学方面，方法是开发和测试新的基因组数据算法，并将高性能计算应用于系统发育分析问题。

ABSTRACTPI Jansen - #0113654PI Moret - #0113095This award provides support for a collaborative project between two biologists (Jansen and Boore) and three computer scientists (Moret, Warnow, and Bader) to develop and test new algorithms and software for constructing evolutionary trees (phylogenies) from the rapidly increasing amount of genomic data. The estimation of phylogenies is crucial to a wide range of basic and applied biological problems such as the epidemiology of AIDS, the identification of viral agents, the analysis of protein structure and function, the prediction of RNA structure; and, of course, it is the basic tool for inferring evolutionary history. Methods for the reconstruction of phylogenies are most commonly applied to DNA sequences. In many cases these sequences change at rates that are too low or too high for recovering accurate evolutionary trees. One new type data that is fast gaining favor in the biology community is gene order and content within whole genomes, but so far very few computational methods have been developed for these types of data. The three goals of the project are to: (1) develop algorithms and software for reconstructing evolutionary trees from gene order and content data; (2) assess the performance of these algorithms through extensive simulation studies under parameter-rich models of genome evolution and through application to real datasets; and (3) develop high-performance implementations of the best algorithms designed in the project using algorithm engineering techniques and a flexible approach to parallelization. This project will make significant contributions in biology, through the development of new models of genome evolution and an improved understanding of the evolution of chloroplast and mitochondrial genomes, and in computer science, through the development and testing of new algorithms for genomic data and the application of high-performance computing to problems in phylogenetic analysis.