Large-Scale Global Alignments Multiple AlignmentsRapid global alignmentSuffix TreesApplication: Find all Matches Between x and ySlide 5Application: Online Search of Strings on a DatabaseApplication: Common Substrings of k StringsSlide 8The Problem: Find a Chain of Local AlignmentsQuadratic Time SolutionQuadratic Time Solution (cont’d)Faster Solution: Sparse DPSparse DPExampleTime AnalysisPutting it All Together: Fast Global Alignment AlgorithmsLAGAN: Pairwise AlignmentLAGANLAGAN: recursive call3. LAGAN: memoryMultiple Sequence AlignmentsSlide 22Slide 23OverviewSlide 25DefinitionMotivationAnother way to view multiple alignmentsSlide 29Scoring FunctionScoring Function (cont’d)Scoring Function: Sum Of PairsSum Of Pairs (cont’d)Slide 34ConsensusSlide 36Multidimensional Dynamic ProgrammingSlide 38Slide 39Large-Scale Global Alignments Multiple AlignmentsLecture 10, Thursday May 1, 2003Lecture 10, Thursday May 1, 2003Rapid global alignmentGenomic regions of interest contain ordered islands of similarity–E.g. genes 1. Find local alignments2. Chain an optimal subset of themLecture 10, Thursday May 1, 2003Suffix Trees•Suffix trees are a method to find all maximal matches between two strings (and much more)Example: x = dabdacd a b d a ccabdaccccadb142563Lecture 10, Thursday May 1, 2003Application: Find all Matches Between x and y1. Build suffix tree for x, mark nodes with x2. Insert y in suffix tree, mark all nodes y “passes from” with y–The path label of every node marked both 0 and 1, is a common substringLecture 10, Thursday May 1, 2003Example of Suffix Tree Construction for x, y1x = d a b d a $y = a b a d a $d a b d a $1. Construct tree for xabda$2$adb3$4$5$6xxx6. Insert a $566. Insert $4. Insert a d a $da$35. Insert d a $y42. Insert a b a d a $ayda$1yyx3. Insert b a d a $ady2a$xLecture 10, Thursday May 1, 2003Application: Online Search of Strings on a DatabaseSay a database D = { s1, s2, …sn }(eg. proteins)Question: given new string x, find all matches of x to database1. Build suffix tree for {s1,…, sn}2. All new queries x take O( |x| ) time(somewhat like BLAST)Lecture 10, Thursday May 1, 2003Application: Common Substrings of k Strings•Say we want to find the longest common substring of s1, s2, …sn 1. Build suffix tree for s1,…, sn2. All nodes labeled {si1, …, sik} represent a match between si1, …, sikMethods to CHAIN Local AlignmentsSparse Dynamic ProgrammingO(N log N)Lecture 10, Thursday May 1, 2003The Problem: Find a Chain of Local Alignments(x,y) (x’,y’)requiresx < x’y < y’Each local alignment has a weightFIND the chain with highest total weightLecture 10, Thursday May 1, 2003Quadratic Time Solution•Build Directed Acyclic Graph (DAG):–Nodes: local alignments (xa,xb) (ya,yb) Directed Edges: any two local alignments that can be chained•Each local alignment is a node vi with alignment score siLecture 10, Thursday May 1, 2003Quadratic Time Solution (cont’d)Dynamic programming:Initialization:Find each node va s.t. there is no edge (u,v0)Set score of V(a) to be saIteration:For each vi, optimal path ending in vi has total score:V(i) = max ( weight(vj, vi) + V(j) )Termination:Optimal global chain: j = argmax ( V(j) ); trace chain from vjWorst case time: quadraticLecture 10, Thursday May 1, 2003Faster Solution: Sparse DP•1,…, N: rectangles•(hj, lj): y-coordinates of rectangle j•w(j): weight of rectangle j•V(j): optimal score of chain ending in j•L: list of triplets (lj, V(j), j)L is sorted by ljyhlLecture 10, Thursday May 1, 2003Sparse DPGo through rectangle x-coordinates, from lowest to highest:1. When on the leftmost end of i:a. j: rectangle in L, with largest lj < hib. V(i) = w(i) + V(j)2. When on the rightmost end of i:a. j: rectangle in L, with largest lj lib. If V(i) > V(j):i. INSERT (li, V(i), i) in Lii. REMOVE all (lk, V(k), k) with V(k) V(i) & lk lixyLecture 10, Thursday May 1, 2003Examplexy1: 53: 32: 64: 45: 22569101112141516Lecture 10, Thursday May 1, 2003Time Analysis1. Sorting the x-coords takes O(N log N)2. Going through x-coords: N steps3. Each of N steps requires O(log N) time:•Searching L takes log N•Inserting to L takes log N•All deletions are consecutive, so log NLecture 10, Thursday May 1, 2003Putting it All Together:Fast Global Alignment Algorithms1. FIND local alignments2. CHAIN local alignments FIND CHAINGLASS: k-mers hierarchical DPMumMer: Suffix Tree Sparse DPAvid: Suffix Tree hierarchical DPLAGAN CHAOS Sparse DPLAGAN: Pairwise Alignment1. FIND local alignments2. CHAIN local alignments3. DP restricted around chainLecture 10, Thursday May 1, 2003LAGAN1. Find local alignments2. Chain -O(NlogN) L.I.S.3. Restricted DPLecture 10, Thursday May 1, 2003LAGAN: recursive call•What if a box is too large?–Recursive application of LAGAN,more sensitive word searchLecture 10, Thursday May 1, 20033. LAGAN: memory“necks” have tiny tracebacks…only store tracebacksMultiple Sequence Multiple Sequence AlignmentsAlignmentsLecture 10, Thursday May 1, 2003Lecture 10, Thursday May 1, 2003Lecture 10, Thursday May 1, 2003Overview•Definition•Scoring Schemes•AlgorithmsMultiple Sequence AlignmentsDefinition and MotivationLecture 10, Thursday May 1, 2003Definition•Given N sequences x1, x2,…, xN:–Insert gaps (-) in each sequence xi, such that•All sequences have the same length L•Score of the global map is maximum•Pairwise alignment: a hypothesis on the evolutionary relationship between the letters of two sequences•Same for a multiple alignment!Lecture 10, Thursday May 1, 2003Motivation•A faint similarity between two sequences becomes very significant if present in many•Protein domains•Motifs responsible for gene regulationLecture 10, Thursday May 1, 2003Another way to view multiple alignments•Pairwise alignment:Good alignment Evolutionary relationship•Multiple alignment:Something in common Sequence in common“inverse” to pairwise alignmentMultiple Sequence AlignmentsScoring FunctionLecture 10, Thursday May 1, 2003Scoring Function•Ideally:–Find alignment that maximizes probability that sequences evolved from common ancestorxyzwv?Lecture 10, Thursday May 1, 2003Scoring Function (cont’d)•Unfortunately: too many parameters•Compromises:–Ignore phylogenetic tree–Statistically independent columns:S(m) = G(m) + i S(mi) m: alignment matrixG: function penalizing gapsLecture 10, Thursday May 1,
View Full Document
Unlocking...