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

“分子序列、进化树和物理映射的高效算法”PI：陶江建议编号：9988353机构：加州大学河滨项目总结-生物、生物医学和制药研究正在经历一场重大革命，因为新的实验方法，如高通量DNA测序，正在产生前所未有的大量基因数据。对这些信息的探索严重依赖于用于数据分析的先进计算方法的发展。从这种依赖关系中，一个新的跨学科研究领域--计算分子生物学--近年来应运而生。该项目旨在研究计算分子生物学几个关键领域中的一些基本算法问题，包括多序列比对、进化树重建、物理映射和DNA测序。多序列比对是同时比较一组(生物分子)序列的标准模型。生物学家经常使用软件工具来计算多序列比对。本项目继续研究一种独特的多序列比对方法，该方法考虑了输入序列的进化历史。目标包括改进的近似方法，以同时计算多序列比对和进化树。对于生物学家和计算机科学家来说，高效、准确的进化树推理一直是一个艰巨的课题。这个项目特别关注基于四元组的进化树重建方法，该方法试图提取关于输入物种的四元组(即四个组)的拓扑信息，然后将这些四元组拓扑重新组合成完整的进化树。将设计有效的近似算法，明确地以最小化输出树和估计的四重组拓扑之间的不一致性为目标。该项目的其他目标包括研究一些组合问题的有效(近似)算法，这些问题是由物理映射和(鸟枪式)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.