Collaborative Research: ITR/AP Reconstructing Complex Evolutionary Histories

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.