Collaborative Research: ITR/AP Reconstructing Complex Evolutionary Histories

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

EIA-0121377Moret, Bernard MUniversity of New MexicoCollaborative Research: ITR/AP: Reconstructing Complex Evolutionary HistoriesReconstruction 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.