Theory and applications of sequence analysis

点击翻译按钮获取中文摘要

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.