Efficient Algorithms for Molecular Sequences, Evolutionary Trees, and Physical Maps

“分子序列的高效算法，进化 树木和物理地图“PI：Tao Jiang建议编号：9988353机构：加州大学河滨分校项目概要--随着新的实验方法，如高通量DNA测序，正在产生前所未有的数量的遗传数据。这些信息的探索严重依赖于先进的数据计算方法的发展从这种依赖性出发，近年来出现了一个新的跨学科研究领域，即计算分子生物学。本项目旨在研究计算分子生物学的几个关键领域中的一些基本算法问题，包括多序列比对、进化树重建、物理作图和DNA测序。多序列比对是生物学家常用的软件工具，本项目继续研究一种考虑输入序列进化历史的独特的多序列比对方法，其目标包括改进近似方法以同时计算多序列比对和进化树。进化树的高效和精确推理一直是生物学家和计算机科学家的一个挑战性课题。该项目特别关注基于四元组的进化树重建方法，该方法试图提取输入物种的四元组（即四个集合）的拓扑信息，然后将这些四元组拓扑重组成完整的进化树。有效的近似算法将被设计，明确的目的是尽量减少输出treeand估计的四重拓扑结构之间的不一致。该项目的其他目标包括研究一些组合问题的有效（近似）算法，这些问题的动机是物理映射和（鸟枪）DNA测序，这是人类基因组计划中的两个基本步骤。一些具体的研究课题包括多重完全消化映射中片段识别的复杂性和最短超弦的近似性，虽然这项研究是理论性的，但其结果可能会在多重序列比对、系统发育推断和限制性内切酶图谱的软件开发中有应用（或影响）。

"Efficient Algorithms for Molecular Sequences, Evolutionary Trees, and Physical Maps"PI: Tao JiangProposal Number: 9988353Institution: University of California-RiversideProject Summary---------------Biological, biomedical and pharmaceutical research is undergoing a majorrevolution as new experimental approaches, such as high-throughput DNAsequencing, are yielding unprecedented amounts of genetic data.The exploration of this information is critically dependent upon the development of advanced computational methods for data analysis.From this dependency, a new interdisciplinary research field, {\em Computational Molecular Biology}, has emerged in recent years. Thisproject aims at investigating some fundamental algorithmic issuesin several key areas of computational molecular biology,including multiple sequence alignment, the reconstruction ofevolutionary trees, physical mapping, and DNA sequencing.Multiple sequence alignment is a standard model for comparing a set of(biomolecular) sequences simultaneously. Software tools for computing multiplesequence alignments are routinely used by biologists.This project continues the study of a unique approach for multiple sequence alignmentthat takes into account the evolutionary history of the input sequences.The objectives include improved approximation methods to compute multiplesequence alignment and evolutionary tree simultaneously. Efficient and accurate inference of evolutionary trees has long been achallenging topic for both biologists and computer scientists. This project is especially focused on quartet-based evolutionary tree reconstructionmethods that attempt to extract topological information about quartets(i.e. sets of four) of input species and then recombine these quartet topologiesinto a full evolutionary tree. Efficient approximation algorithms will be devised that explicitly aim at minimizing the inconsistency between the output treeand the estimated quartet topologies. The other objectives of the project include the study of efficient (approximation)algorithms for some combinatorial problems that are motivated by physical mapping and(shotgun) DNA sequencing, which are two fundamental steps in the Human Genome Project. Some specific topics to be studied include the complexity of fragment identificationin multiple complete digest mapping with bounded multiplicity and the approximationof (vairants of) shortest superstrings.Although this research is theoretical in nature, its results will likely have applications (or implications) in the development of software toolsfor multiple sequence alignment, phylogenetic inference, and restriction mapping.