Algorithms for Molecular Biology Hidden Markov Models Shamir英文电子书.pdf

Algorithms for Molecular Biology Fall Semester, 2001 Lecture 5: December 13, 2001 Lecturer: Ron Shamir Scribe: Roi Yehoshua and Oren Danewitz 1 5.1 Hidden Markov Models 5.1.1 Preface: CpG islands CpG is a pair of nucleotides C and G, appearing successively, in this order, along one DNA strand. It is known that due to biochemical considerations CpG is relatively rare in most DNA sequences [4]. However, in particular short subsequences, which are several hundreds of nucleotides long, the couple CpG is more frequent. These subsequences, called CpG islands, are known to appear in biologically more significant parts of the genome, such as around the promoters or ’start’ regions of many genes. The ability to identify these CpG islands in the DNA will therefore help us spot the more significant regions of interest along the genome. We will consider two problems involving CpG islands : First, given a short genome se- quence, decide if it comes from a CpG island or not. Second, given a long DNA sequence, locate all the CpG islands in it. 5.1.2 Reminder: Markov chains Definition A Markov chain is a triplet (Q, {p (x1 = s)}, A), where: • Q is a finite set of states. Each state corresponds to a symbol in the alphabet Σ. • p is the initial state probabilities. • A is the state transition probabilities, denoted by ast for each s, t ∈ Q. For each s, t ∈ Q the transition probability is: ast ≡ P (xi = t |xi−1 = s) (5.1) 1This scribe is partially based on Ophir Gvirtzer’s and Zohar Ganon’s scribe from Fall Semester 2000. c 2