Genome RearrangementsOutlineGenome Rearrangements Example I: Turnip vs CabbageSlide 4Turnip vs Cabbage: Almost Identical mtDNA gene sequencesTurnip vs Cabbage: Different mtDNA Gene OrderSlide 7Slide 8Slide 9Slide 10Transforming Cabbage into TurnipGenome Rearrangements Example II: Human vs. MouseHistory of Chromosome XMouse vs Human GenomeTypes of RearrangementsReversalsReversalsSlide 18Slide 19Reversals: ExampleReversal Distance ProblemSorting By Reversals Problem [s = (1 2 … n )]Sorting By Reversals: ExampleSorting by reversalsSorting by reversals Most parsimonious scenariosSorting By Reversals: A Greedy AlgorithmSlide 27Greedy Algorithm: PseudocodeAnalyzing SimpleReversalSortSlide 30BreakpointsBreakpoints: An ExampleExtending PermutationsReversal Distance and BreakpointsSorting By Reversals: A Better Greedy AlgorithmStripsStrips: An ExampleThings To ConsiderThings To Consider (cont’d)Slide 40Slide 41ImprovedBreakpointReversalSortImprovedBreakpointReversalSort: Performance GuaranteeSigned PermutationsGRIMM Web ServerSlide 46What You Should Know1Genome Rearrangements (Lecture for CS498-CXZ Algorithms in Bioinformatics) Dec. 6, 2005ChengXiang ZhaiDepartment of Computer ScienceUniversity of Illinois, Urbana-Champaign2Outline•The Problem of Genome Rearrangements•Sorting By Reversals•Greedy Algorithm for Sorting by Reversals–Position-based –Breakpoint-based3Genome Rearrangements Example I:Turnip vs Cabbage•Although cabbages and turnips share a recent common ancestor, they look and taste different4Turnip vs Cabbage: Comparing Gene Sequences Yields No Evolutionary Information5Turnip vs Cabbage: Almost Identical mtDNA gene sequences•In 1980s Jeffrey Palmer studied evolution of plant organelles by comparing mitochondrial genomes of the cabbage and turnip•99% similarity between genes•These surprisingly identical gene sequences differed in gene order•This study helped pave the way to analyzing genome rearrangements in molecular evolution6Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:7Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:8Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:9Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:10Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:BeforeAfterEvolution is manifested as the divergence in gene order11Transforming Cabbage into Turnip12•What are the similarity blocks and how to find them?•What is the architecture of the ancestral genome?•What is the evolutionary scenario for transforming one genome into the other?Unknown ancestor~ 75 million years agoMouse (X chrom.)Human (X chrom.)Genome Rearrangements Example II:Human vs. Mouse13History of Chromosome XRat Consortium, Nature, 200414Mouse vs Human Genome•Humans and mice have similar genomes, but their genes are ordered differently•~245 rearrangements–Reversal, fusion, fission, translocation•Reversal: flipping a block of genes within a genomic sequence15Types of RearrangementsReversal1 2 3 4 5 6 1 2 -5 -4 -3 6Translocation1 2 3 44 5 61 2 6 4 5 3 1 2 3 4 5 61 2 3 4 5 6FusionFissionChromosome 1:Chromosome 2:Chromosome 1:Chromosome 2:16Reversals•Blocks represent conserved genes.•In the course of evolution blocks 1,…,10 could be misread as 1, 2, 3, -8, -7, -6, -5, -4, 9, 10.•Rearrangements occurred about once-twice every million years on the evolutionary path between human and mouse.132410568971, 2, 3, 4, 5, 6, 7, 8, 9, 1017Reversals132410568971, 2, 3, -8, -7, -6, -5, -4, 9, 10Blocks represent conserved genes.In the course of evolution or in a clinical context, blocks 1,…,10 could be misread as 1, 2, 3, -8, -7, -6, -5, -4, 9, 10.Reversals occurred one-two times every million years on the evolutionary path between human and mouse.18Reversals132410568971, 2, 3, -8, -7, -6, -5, -4, 9, 10The reversion introduced two breakpoints(disruptions in order).19Reversals•Let’s first assume that genes in genome do not have direction1------ i-1 i i+1 ------j-1 j j+1 -----n`1------ i-1 j j-1 ------i+1 i j+1 -----nReversal ( i, j ) reverses the elements from i to j in and transforms into `,j)20Reversals: Example•Example: = 1 2 3 4 5 6 7 8 (3,5) ’= 1 2 5 4 3 6 7 821Reversal Distance Problem•Goal: Given two permutations, find the shortest series of reversals that transforms one into another•Input: Permutations and •Output: A series of reversals 1,…t transforming into such that t is minimum•t - reversal distance between and •d(, ) - smallest possible value of t, given and 22Sorting By Reversals Problem[(1 2 … n )] •Goal: Given a permutation, find a shortest series of reversals that transforms it into the identity permutation (1 2 … n ) •Input: Permutation •Output: A series of reversals 1, … t transforming into the identity permutation such that t is minimum23Sorting By Reversals: Example•t =d( ) - reversal distance between and •Example : input: = 3 4 2 1 5 6 7 10 9 8 output: 4 3 2 1 5 6 7 10 9 8 4 3 2 1 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 So d( ) = 324Sorting by reversalsStep 0: 2 -4 -3 5 -8 -7 -6 1Step 1:2 3 4 5 -8 -7 -6 1Step 2:2 3 4 5 6 7 8 1Step 3:2 3 4 5 6 7 8 -1Step 4:-8 -7 -6 -5 -4 -3 -2 -1Step 5: 1 2 3 4 5 6 7 825Sorting by reversalsMost parsimonious scenariosStep 0: 2 -4 -3 5 -8 -7 -6 1Step 1:2 3 4 5 -8 -7 -6 1Step 2:-5 -4 -3 -2 -8 -7 -6 1Step 3:-5 -4 -3 -2 -1 6 7 8Step 4: 1 2 3 4 5 6 7 8The reversal distance is the minimum number of reversals required to transform into .Here, the reversal distance is d=4.26Sorting By Reversals: A Greedy Algorithm•If sorting permutation = 1 2 3 6 4 5, the first three numbers are already in order so it does not make any sense to break them. These already sorted numbers of will be defined as prefix()– prefix() = 3•This results in an idea for a greedy algorithm: increase prefix() at every step27•Doing so, can be sorted 1 2 3 6 4 5 1 2 3 4 6
View Full Document
Unlocking...