生物资讯相关演算法Algorithms in Bioinformatics.pptVIP

2003/9/30 Algorithms in Bioinformatics, Lecture 2 生物資訊相關演算法Algorithms in Bioinformatics 呂學一 (中央研究院 資訊科學所) .tw/~hil/ Reminder: Homework #1 The deadline is extended to 11:59pm, Tuesday, 9/30, 2003. Late submissions receive half of the grades for this homework. For those who not taking this course (e.g., just sitting in for fun): Please do Step 1 so that you will receive broadcast message about this course. If you don’t mind having interaction with me during the lectures, you are strongly encouraged to do Step 2 any time in this semester. Our time frame According to NTU’s new design Start: 10:20AM End: 1:10PM Two 10-minute breaks in between. Today Part 1 – Exact string matching Part 2 – Suffix tree (motivation) Part 1 – Exact string matching What, why, and how? A. What? String versus Sequence String a segment of consecutive characters. usually called sequence in Biology. Sequence need not be consecutive. Example: S = “a t g a t g c a a t” Substrings of S: “g a t g c”, “t g c a a t”. Subsequences of S: “a g g t”, “a a a a”. The Exact String Matching Problem Input a string P –– the pattern a string S –– the text Output all the occurrences of P in S. Illustration 1 2 3 4 5 6 7 8 9 0 1 2 3 S = t a t a t t a t a t a t a P = t a t a Output 1 6 8 10 B. Why? Computer Science Dictionary, database Search engines: Yahoo!, Google, … Biology: Blast Warm-up for this course: A well studied problem, The idea/technique behind. C. How? Notation for strings S is a string |S| = the length of S. substring: S[i…j]. A na?ve algorithm Input: S and P. Output: all occurrences of P in S. for i=1 to |S| if S[i…i+|P|-1] equals P output i; Illustration 1 2 3 4 5 6 7 8 9 0 1 2 3 S = t a t a t t a t a t a t a P = t a t a Output 1 6 8 10 Time complexity? Input: S and P. Output: all occurrences of P in S. for i=1 to |S| if S[i…i+|P|-1] equals P then output i; O(|S|2 |P|) O(|S| |P|) O(|P| log|S|) O(|S| + |P|) Tightness of the time complexity O(|S| |P|) is ti