Multiple AlignmentOutlineMultiple Alignment versus Pairwise AlignmentSlide 4Slide 5Generalizing the Notion of Pairwise AlignmentAlignments = Paths in…Alignment PathsSlide 9Slide 10Aligning Three Sequences2-D vs 3-D Alignment Grid2-D cell versus 2-D Alignment CellArchitecture of 3-D Alignment CellMultiple Alignment: Dynamic ProgrammingMultiple Alignment: Running TimeMultiple Alignment Induces Pairwise AlignmentsReverse Problem: Constructing Multiple Alignment from Pairwise AlignmentsSlide 19Inferring Multiple Alignment from Pairwise AlignmentsCombining Optimal Pairwise Alignments into Multiple AlignmentProfile Representation of Multiple AlignmentSlide 23Aligning alignmentsSlide 25Multiple Alignment: Greedy ApproachGreedy Approach: ExampleGreedy Approach: Example (cont’d)Slide 29Progressive AlignmentClustalWStep 1: Pairwise AlignmentStep 2: Guide TreeStep 2: Guide Tree (cont’d)Step 3: Progressive AlignmentMultiple Alignments: ScoringMultiple LCS ScoreEntropyEntropy: ExampleMultiple Alignment: Entropy ScoreEntropy of an Alignment: ExampleSlide 42Inferring Pairwise Alignments from Multiple AlignmentsMultiple Alignment ProjectionsSum of Pairs Score(SP-Score)Computing SP-ScoreSP-Score: ExampleMultiple Alignment: HistoryProblems with Multiple AlignmentPOA vs. Classical Multiple Alignment ApproachesAlignment as a GraphSolution: Representing Sequences as Paths in a GraphPartial Order Multiple AlignmentPartial Order Alignment (POA) AlgorithmPO-PO AlignmentDynamic Programming for Aligning Two Directed GraphsRow-Column AlignmentPOA AdvantagesA-Bruijn Alignment (ABA)ABAABA vs. POA vs. MSAAdvantages of ABAABA: multiple alignments of proteinCreditswww.bioalgorithms.infoAn Introduction to Bioinformatics AlgorithmsMultiple AlignmentAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoOutline•Dynamic Programming in 3-D •Progressive Alignment•Profile Progressive Alignment (ClustalW)•Scoring Multiple Alignments•Entropy•Sum of Pairs Alignment•Partial Order Alignment (POA)•A-Bruijin (ABA) Approach to Multiple AlignmentAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoMultiple Alignment versus Pairwise Alignment•Up until now we have only tried to align two sequences.An Introduction to Bioinformatics Algorithms www.bioalgorithms.infoMultiple Alignment versus Pairwise Alignment•Up until now we have only tried to align two sequences. •What about more than two? And what for?An Introduction to Bioinformatics Algorithms www.bioalgorithms.infoMultiple Alignment versus Pairwise Alignment•Up until now we have only tried to align two sequences. •What about more than two? And what for? •A faint similarity between two sequences becomes significant if present in many•Multiple alignments can reveal subtle similarities that pairwise alignments do not revealAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoGeneralizing the Notion of Pairwise Alignment•Alignment of 2 sequences is represented as a 2-row matrix•In a similar way, we represent alignment of 3 sequences as a 3-row matrix A T _ G C G _ A _ C G T _ A A T C A C _ A•Score: more conserved columns, better alignmentAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoAlignments = Paths in…•Align 3 sequences: ATGC, AATC,ATGCA A T -- CA -- T G C-- A T G CAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoAlignment Paths0 1 1 2 3 4A A T -- CA -- T G C-- A T G Cx coordinateAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoAlignment Paths•Align the following 3 sequences: ATGC, AATC,ATGC0 1 1 2 3 40 1 2 3 3 4A A T -- CA -- T G C-- A T G C• x coordinatey coordinateAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoAlignment Paths0 1 1 2 3 40 1 2 3 3 4A A T -- CA -- T G C0 0 1 2 3 4-- A T G C• Resulting path in (x,y,z) space: (0,0,0)(1,1,0)(1,2,1) (2,3,2) (3,3,3) (4,4,4)x coordinatey coordinatez coordinateAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoAligning Three Sequences•Same strategy as aligning two sequences•Use a 3-D “Manhattan Cube”, with each axis representing a sequence to align•For global alignments, go from source to sinksourcesinkAn Introduction to Bioinformatics Algorithms www.bioalgorithms.info2-D vs 3-D Alignment GridVW2-D edit graph3-D edit graphAn Introduction to Bioinformatics Algorithms www.bioalgorithms.info2-D cell versus 2-D Alignment Cell In 3-D, 7 edges in each unit cubeIn 2-D, 3 edges in each unit squareAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoArchitecture of 3-D Alignment Cell(i-1,j-1,k-1)(i,j-1,k-1)(i,j-1,k)(i-1,j-1,k)(i-1,j,k)(i,j,k)(i-1,j,k-1)(i,j,k-1)An Introduction to Bioinformatics Algorithms www.bioalgorithms.infoMultiple Alignment: Dynamic Programming•si,j,k = max(x, y, z) is an entry in the 3-D scoring matrixsi-1,j-1,k-1 + (vi, wj, uk)si-1,j-1,k +  (vi, wj, _ )si-1,j,k-1 +  (vi, _, uk)si,j-1,k-1 +  (_, wj, uk)si-1,j,k +  (vi, _ , _)si,j-1,k +  (_, wj, _)si,j,k-1 +  (_, _, uk)cube diagonal: no indelsface diagonal: one indeledge diagonal: two indelsAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoMultiple Alignment: Running Time•For 3 sequences of length n, the run time is 7n3; O(n3)•For k sequences, build a k-dimensional Manhattan, with run time (2k-1)(nk); O(2knk)•Conclusion: dynamic programming approach for alignment between two sequences is easily extended to k sequences but it is impractical due to exponential running timeAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoMultiple Alignment Induces Pairwise AlignmentsEvery multiple alignment induces pairwise alignments x: AC-GCGG-C y: AC-GC-GAG z: GCCGC-GAGInduces:x: ACGCGG-C; x: AC-GCGG-C; y: AC-GCGAGy: ACGC-GAC; z: GCCGC-GAG; z: GCCGCGAGAn Introduction to Bioinformatics Algorithms www.bioalgorithms.infoReverse Problem: Constructing Multiple Alignment from Pairwise AlignmentsGiven 3 arbitrary pairwise alignments: x: ACGCTGG-C; x: AC-GCTGG-C; y: AC-GC-GAGy: ACGC--GAC; z: GCCGCA-GAG; z: GCCGCAGAG can we construct a multiple alignment that inducesthem?An Introduction to Bioinformatics Algorithms www.bioalgorithms.infoReverse Problem: Constructing Multiple Alignment from Pairwise AlignmentsGiven 3 arbitrary pairwise alignments: x: ACGCTGG-C; x: AC-GCTGG-C; y: AC-GC-GAGy: ACGC--GAC; z: GCCGCA-GAG; z: GCCGCAGAG can we construct a multiple alignment that