New version page

CU-Boulder CSCI 7000 - Genome Rearrangements

This preview shows page 1-2-3-4-29-30-31-32-59-60-61-62 out of 62 pages.

View Full Document
View Full Document

End of preview. Want to read all 62 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

Genome RearrangementsTurnip vs CabbageSlide 3Turnip vs Cabbage: Different mtDNA Gene OrderSlide 5Slide 6Slide 7Turnip vs Cabbage: Gene Order ComparisonTransforming Cabbage into TurnipReversalsTypes of MutationsTypes of RearrangementsSlide 13Slide 14Genome rearrangementsWhy do we care?SKY (spectral karyotyping)Robertsonian TranslocationSlide 19Philadelphia ChromosomeSlide 21InversionSlide 23Colon cancerColon CancerComparative Mapping: Mouse vs Human GenomeWaardenburg’s Syndrome: Mouse Provides Insight into Human Genetic DisorderWaardenburg’s syndrome and splotch miceReversals: ExampleSlide 30Reversals and Gene OrdersReversal Distance ProblemSorting By Reversals ProblemSorting by reversals Example: 5 stepsSorting by reversals Example: 4 stepsPancake Flipping ProblemSorting By Reversals: A Greedy AlgorithmSlide 38Greedy Algorithm: PseudocodeAnalyzing SimpleReversalSortSlide 41Approximation AlgorithmsApproximation Ratio / Performance GuaranteeAdjacencies and BreakpointsBreakpoints: An ExampleAdjacency & BreakpointsExtending PermutationsReversal Distance and BreakpointsSorting By Reversals: A Better Greedy AlgorithmStripsReducing the Number of BreakpointsThings To ConsiderSlide 53Slide 54Slide 55Reducing the Number of Breakpoints AgainThings To Consider (cont’d)ImprovedBreakpointReversalSortPerformance GuaranteeSigned PermutationsSigned PermutationSigned permutations are easier!Genome RearrangementsCSCI 7000-005: Computational GenomicsDebra [email protected] vs Cabbage•Share a recent common ancestor •Look and taste differentTurnip vs Cabbage•Comparing mtDNA gene sequences yields no evolutionary information•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 evolutionTurnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:Turnip vs Cabbage: Different mtDNA Gene Order•Gene order comparison:Turnip vs Cabbage: Gene Order ComparisonBeforeAfter•Evolution is manifested as the divergence in gene orderTransforming Cabbage into TurnipReversals132410568971, 2, 3, -8, -7, -6, -5, -4, 9, 10Blocks 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.1, 2, 3, 4, 5, 6, 7, 8, 9, 10Blocks represent conserved genes.Types of MutationsTypes of RearrangementsReversal1 2 3 4 5 6 1 2 -5 -4 -3 6Types of RearrangementsTranslocation1 2 3 44 5 61 2 6 4 5 3Types of Rearrangements1 2 3 4 5 61 2 3 4 5 6FusionFission•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 rearrangementsWhy do we care?SKY (spectral karyotyping)Robertsonian Translocation13 14Robertsonian Translocation•Translocation of chromosomes 13 and 14•No net gain or loss of genetic material: normal phenotype. •Increased risk for an abnormal child or spontaneous pregnancy loss13 14Philadelphia Chromosome922Philadelphia Chromosome•Seen in about 90% of patients with Chronic myelogenous leukemia (CML)•A translocation between chromosomes 9 and 22 (part of 22 is attached to 9)9 22Inversion16Inversion•Chromosome on the right is inverted near the centromere16Colon cancerColon CancerComparative Mapping: Mouse vs Human Genome•Humans and mice have similar genomes, but their genes are ordered differently•~245 rearrangements–Reversals–Fusions–Fissions–TranslocationsWaardenburg’s Syndrome: Mouse Provides Insight into Human Genetic Disorder•Characterized by pigmentary dysphasia•Gene implicated linked to human chromosome 2 •It was not clear where exactly on chromosome 2Waardenburg’s syndrome and splotch mice•A breed of mice (with splotch gene) had similar symptoms caused by the same type of gene as in humans•Scientists identified location of gene responsible for disorder in mice•Finding the gene in mice gives clues to where same gene is located in humansReversals: Example  = 1 2 3 4 5 6 7 8  1 2 5 4 3 6 7 8Reversals: Example  = 1 2 3 4 5 6 7 8  1 2 5 4 3 6 7 8 1 2 5 4 6 3 7 8Reversals and Gene Orders•Gene order represented by permutation 1------ i-1 i i+1 ------j-1 j j+1 -----n     1------ i-1 j j-1 ------i+1 i j+1 -----nReversal ( i, j ) reverses (flips) the elements from i to j in  ,j)Reversal Distance Problem•Goal: Given two permutations, find shortest series of reversals to transform 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  Sorting By Reversals Problem•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 minimum•min t =d( ) = reversal distance of Sorting by reversalsExample: 5 stepsSorting by reversalsExample: 4 stepsStep 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 8What is the reversal distance for this permutation? Can it be sorted in 3 steps?Pancake Flipping Problem•Chef prepares unordered stack of pancakes of different sizes•The waiter wants to sort (rearrange) them, smallest on top, largest at bottom•He does it by flipping over several from the top, repeating this as many times as necessaryChristos Papadimitrou and Bill Gates flip pancakesSorting By Reversals: A Greedy Algorithm•Example:


View Full Document
Loading Unlocking...
Login

Join to view Genome Rearrangements and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Genome Rearrangements and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?