Statistical Mechanics of Sequence Matching

这是一项新的资助，由材料研究、分子和细胞生物学部门与数学和物理科学局的多学科活动办公室共同资助。这个理论项目将应用统计力学和非平衡动力学的方法来阐明DNA和蛋白质序列匹配问题的统计和相图。在最近的一系列研究中发现，广泛使用的序列比对算法，如Smith-Waterman算法，类似于统计物理中的一些常见问题，即随机和相关介质中有向路径的钉扎，以及噪声环境中生长表面的非平衡粗糙化。这个类比提出了一种与目前计算生物学所采用的方法非常不同的序列比对方法。将开发新的分析方法来计算随机和相互关联的序列比对的相图的近似形式和各种特征标度的大小。由序列相关性引起的相图中的移位将被用来确定用于检测同源序列的最佳参数区域。此外，将使用一种经验方法来从单个序列对的比对中快速提取罕见事件的统计信息(而不是从整体中收集统计信息，比如通过序列的随机洗牌)。这种方法应能有效地确定每一排列的统计意义。随后通过改变得分参数来优化该显着值，然后应产生对弱序列同源性敏感的所需的高保真比对。还将研究现有算法的扩展，以考虑长范围序列内相关性、插入/删除的长片段以及多个接近最佳匹配的区域。最后，正在开发的用于序列比对的概念方法和数学方法也可以用于理解长DNA分子的物理结合。后者提出了一些新的统计力学问题，这些问题本身就值得研究。这门学科为新一代跨学科物理学家提供了一个极好的培训基础，他们将学习和应用现代统计力学的复杂方法，同时欣赏和发现分子生物学中有趣的当前问题。这是一笔新的赠款，由材料研究、分子和细胞生物学部门与数学和物理科学局的多学科活动办公室共同资助。这个理论项目将应用统计力学和非平衡动力学的方法来阐明DNA和蛋白质序列匹配问题的统计和相图。这笔赠款为新一代跨学科物理学家提供了一个极好的培训基础，他们将学习和应用现代统计力学的复杂方法，同时欣赏和发现分子生物学中有趣的当前问题。

9971456HwaThis is a new grant funded jointly by the Divisions of Materials Research and Molecular and Cellular Biology with the Directorate of Mathematical and Physical Science's Office of Multidisciplinary Activities. This theoretical project will apply the methods of statistical mechanics and nonequilibrium dynamics to elucidate the statistics and phase diagram of DNA and protein sequence matching problems. In a series of recent studies it has been found that the widely used sequence alignment algorithms, e.g., the Smith-Waterman algorithm, are analogous to some familiar problems in statistical physics, namely, the pinning of a directed path in random and correlated media, and the nonequilibrium roughening of growing surfaces in a noisy environment. This analogy suggests an approach to sequence alignment that is very different from the current one taken in computational biology. New analytical methods will be developed to calculate the approximate form of the phase diagram and the magnitude of various charcteristic scales for the alignment of random and mutually correlated sequences. The shift in phase diagram due to sequence correlations will be used to pinpoint the optimal parameter regime for detecting homologous sequences. Also, an empirical method will be used to extract the rare-event statistics quickly from the alignment of individual sequence pairs (rather than collecting statistics from an ensemble, say, via the random shuffling of sequences). This method should lead to efficient determination of the statistical significance of each alignment. Subsequent optimization of this significance value by varying score parameters should then yield the desired high-fidelity alignment sensitive to weak sequence homologies. Extension of existing algorithms to take into account long-range intra-sequence correlations, long segments of insertion/deletions, and multiple regions of near-optimal matchings will also be studied. Lastly, the conceptual approach and mathematical methods being developed for sequence alignment can also be applied to understand the physical association of long DNA molecules. The latter suggests a number of novel problems of statistical mechanics which are interesting to study in their own right. This subject provides an excellent training ground for a new generation of interdisciplinary physicists, who will learn and apply the sophisticated methods of modern statistical mechanics, and at the same time, appreciate and discover interesting current problems in molecular biology. This is a new grant funded jointly by the Divisions of Materials Research and Molecular and Cellular Biology with the Directorate of Mathematical and Physical Science's Office of Multidisciplinary Activities. This theoretical project will apply the methods of statistical mechanics and nonequilibrium dynamics to elucidate the statistics and phase diagram of DNA and protein sequence matching problems. The grant provides an excellent training ground for a new generation of interdisciplinary physicists, who will learn and apply the sophisticated methods of modern statistical mechanics, and at the same time, appreciate and discover interesting current problems in molecular biology.