Theory and applications of sequence analysis

离散序列在各种环境中用于科学分析，从生物序列(如DNA或RNA序列)到音乐序列(如乐谱中的音符)，再到文本序列(如文档中的单词)。对于自然发生的序列，进化或其他过程嵌入其中的信息是什么？对于人造序列，有意或无意地将什么模式强加到序列中？常用工具被用来分析这种序列。一种工具是隐马尔可夫模型(HMM)，发明用于将语音记录解码为音素，但其用途已扩展到检测DNA序列中的基因，识别音乐表演或配乐的相似性，或对地震事件进行分类。 我们将推进我们对HMM这样的概率系统的理论理解。最近关于HMM解码的工作确定了维特比算法发现的最可能路径的属性，但这是高度技术性的数学。对于生物信息学中重要的隐马尔可夫模型，它能被简化或扩展吗？ 其次，我们研究了在隐马尔可夫模型和其他概率结构中学习和推理的新方法。隐马尔可夫模型中的稳健解码使我们能够专注于寻找可能与真实的注释“接近”的注释，而不是仅仅识别序列在隐马尔可夫模型中最可能的状态路径。我们将提出这些译码算法，并将它们用于各种应用中。稳健的HMM解码是从生物信息学到声学等领域的关键需求。 最后，我们将重点介绍新的和经典的应用程序。其中一个重点仍然是DNA和蛋白质的比对，但我们将把我们的应用扩展到音乐信息检索、DNA和RNA序列中重组点的检测(应用于寻找进化热点和HIV序列中的重组)，以及预测具有生物重要性的分子结构。 我们的工作是在新信息时代一些最有趣的领域的交叉点上，为工业和学术界的职业生涯培养研究生。

Discrete sequences arrive in scientific analysis in a variety of contexts, from biological sequences such as DNA or RNA sequences, to musical sequences such as the notes found in a score, to text sequences, such as the words of a document. For naturally-occuring sequences, what is the information that evolution or other processes has embedded in them? For man-made sequences, what patterns are imposed into the sequence, deliberately or not? Common tools are used to analyze such sequences. One tool is hidden Markov models (HMMs), invented to decode speech recordings into phonemes, but whose use has spread to detecting genes in DNA sequences, identifying similarities in musical performances or scores, or classifying seismic events. We will advance our theoretical understanding of probabilistic systems like HMMs. Recent work on HMM decoding identifies properties of the most likely path, discovered by the Viterbi algorithm, but it is highly technical mathematics. Can it be simplified or expanded for HMMs important in bioinformatics? Second, we study new methods for learning and inferring in HMMs and other probabilistic structures. Robust decoding in HMMs lets us focus on finding annotations likely to be "close" to the true one, rather than just identifying the most probable state path in an HMM for a sequence . We will draw out these decoding algorithms, and use them in a variety of applications. Robust HMM decoding is a key need in domains from bioinformatics to acoustics. Finally, we will focus on applications both new and classical. One focus remains DNA and protein alignment, but we will spread our applications to music information retrieval, detection of recombination points in DNA and RNA sequences (with applications to finding evolutionary hotspots and recombinations in HIV sequences), and predicting the structure of biologically important molecules. Our work trains graduate students for careers in industry and academia at the intersection of some of the most interesting areas of the new information age.