Statistical Mechanics of Sequence Matching

9971456 hwa这是一项由材料研究和分子细胞生物学部门与数学和物理科学理事会多学科活动办公室联合资助的新拨款。本理论项目将运用统计力学和非平衡动力学的方法来阐明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.