Collaborative Research: ITR/AP Reconstructing Complex Evolutionary Histories

EIA-0121680 Warnow，Tandy J德克萨斯大学奥斯汀分校合作研究：ITR/AP：重建复杂的进化一组生物体进化历史的重建改变了生物学的面貌，并越来越多地用于药物发现，流行病学和基因工程。不幸的是，这种重建通常涉及解决困难的优化问题，因此即使是中等规模的数据集也可能需要数月至数年的计算。 此外，目前几乎所有的进化重建都假设历史模式是一种严格的分歧，可以用二叉树来表示。 这一假设经常被违背，特别是植物，它们经常很容易杂交，从而产生关系网络。这个项目汇集了来自两个机构的计算机科学家和生物学家，开发新的模型和算法来解决这两个问题。 该项目的成功完成将产生巨大的影响，提供工具，用于重建大型数据集的遗传学，并推断适合杂交物种形成的进化网络模型的第一个工具。 这种网络模型将改变生物学家对物种形成的看法，而大规模分析方法的发展将大大有利于医疗和制药实践。 信息技术也将在根本上得到推进，因为该项目将展示算法设计和高性能算法工程如何共同解决非常困难的离散优化问题。

EIA-0121680Warnow, Tandy JUniversity of Texas at AustinCollaborative Research: ITR/AP: Reconstructing Complex EvolutionaryReconstruction of the evolutionary history of a group of organisms has changed the face of biology and is being used increasingly in drug discovery, epidemiology, and genetic engineering. Unfortunately, such reconstructions typically involve solving difficult optimization problems, so that even moderately large datasets can require months to years of computation. In addition, almost all evolutionary reconstructions presently assume that the historical pattern is one of strict divergence that can be represented by a binary tree. This assumption is frequently violated, especially by plants which often hybridize readily and thus produce networks of relationships.This project brings together computer scientists and biologists from two institutions to develop new models and algorithms to address these two problems. Successful completion of this project will have an enormous impact by providing tools for reconstructing phylogenies of large datasets, and the first tools for inferring network models of evolution appropriate to hybridizing speciation. Such network models will alter how biologists think about speciation, while the development of methods for large-scale analyses will strongly benefit medical and pharmaceutical practice. Information technology will be advanced in fundamental ways as well, as the project will demonstrate how algorithm design and high-performance algorithm engineering can jointly solve very difficult discrete optimization problems.