Of Mice and Men Learning from genome reversal findingsReversal Distance – The minimum number of reversals to translate from one genome to another Syntney Block – region in which the same gene order is observed between species Ortholog – corresponding gene in two different speciesOverviewWhat are we solving?ReversalsBreakpointsReversal Distance: Guess #1Reality and Desire ConstructionReality and Desire DiagramReversal Distance: Guess #2ComponentsYou Are HereConverging and DivergingConverge? Diverge? So what?The Good and the BadSome “Bad” ExamplesSlide 17HurdlesExample HurdlesSlide 20Super/Simple HurdlesThe FortressExample FortressReversal Distance: Guess #3ReferencesFirst PaperFirst Paper OverviewThe ProcessWhole GenomeSecond PaperSecond Paper OverviewConventional WisdomDo we have a match?Micro-rearrangement EvidenceCalculating Breakpoint ReuseStatistical EvidenceQuestions?Of Mice and MenLearning from genome reversal findingsGenome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse GenomesandTransforming Men into Mice: the Nadeau-Taylor Chromosomal Breakage Model Revisitedboth papers written by Pavel Pevzner and Glenn TeslerReversal Distance – The minimum number of reversals to translate from one genome to anotherSyntney Block – region in which the same gene order is observed between speciesOrtholog – corresponding gene in two different speciesBasic, Basic TermsOverview● Theory of reversal distance calculation● A new model for presenting reversal information (primary topic of Genome Rearrangements in Mammalian Evolution)● Evidence of “fragile” genome regions (primary topic of (Transforming Men into Mice)What are we solving?Find d(), the reversal distance, from permutation to permutation where is L 4 5 2 1 3 6 R is L 1 2 3 4 5 6 RReversalsA reversal operation, , is defined as follows: = [ i , j ](k) = { ( i + j - k ) if i < k < j, (k) otherwise}BreakpointsL 1 3 2 4 5 6 RA breakpoint of with respect to is a pair x, y of elements of Lº such that xy appears in the extended version of , but neither xy nor the reverse pair yx appear in the extended .Reversal Distance: Guess #1d() > b() / 2...we can do better than that!Reality and Desire ConstructionExtended Reality and Desire EdgesTerminalsReality EdgesReality and Desire DiagramReality and Desire Diagram - RD()c() = # of CyclesReversal Distance: Guess #2d() > n + 1 - c()Try taking a closer look...ComponentsComponent – set of interleaving cycles (cycles which cross in a reality and desire diagram)This reality and desire diagram has six components.You Are HereConverging and Diverging●Edges A, C, and E, converge●Edges D and F diverge●Edges B and D diverge●Edges F and B convergeConverge? Diverge? So what?Let = [ e , f ] and act on RD()...If edges e and f belong to different cycles,then c() = c() – 1If edges e and f belong to the same cycle and converge,then c() = c()If edges e and f belong to the same cycle and diverge,then c() = c() + 1The Good and the BadGood Components contain at least one Good Cycle.Bad Components contain only Bad Cycles.Good Cycles contain at least one pair of diverging edges.Bad Cycles contain only converging edges.Some “Bad” ExamplesThis reality and desire diagram has five bad components and only one good component (bottom).The good component has one good cycle and one bad cycle.You Are HereHurdlesHurdle – a bad component that does not separate any other two bad componentsNonhurdle – a bad component that does separate at least two bad componentsExample HurdlesIn this example...● A, F, C, and D are hurdles.● E and B are nonhurdles.● h() = 4You Are HereSuper/Simple HurdlesIn this example...● Hurdle F protects nonhurdle E● F is a super hurdle● A, C, and D are simple hurdles● h() = 4The FortressFortress – A permutation whose reality and desire diagram contains an odd number of hurdles and all of them are super hurdles.f( = 1{ is a fortress}Example FortressSmallest Possible fortress:Reversal Distance: Guess #3d() = n + 1 – c() + h() + f()Finally!!!ReferencesThe preceding material was taken from Introduction to Computational Molecular Biology by Setubal and Meidanis, based on the following papers:●V. Bafna and P. A. Pevzner – Genome rearrangements and sorting by reversals.●S. Hannenhalli and P. A. Pevzner – Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals) (this paper referenced in text of Transforming Men into Mice for definitions of hurdles and fortresses)●J. D. Kececioglu and D. Sankoff – Exact and approximate algorithms for sorting by reversals with application to genome rearrangementFirst PaperGenome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse GenomesPavel Pevzner and Glenn TeslerFirst Paper OverviewThis paper presents a new kind of graph which achieves the usefulness of reality and desire diagrams on simple genome comparison graphs.The ProcessGRIMM-Synteny AlgorithmUseful features:● Same cycle count as reality desire diagram!● Cycles of more than for edges indicate reused breakpoints!WholeGenomeResultsSynteny Blocks: 281Reversal Distance: 245Second PaperTransforming Men into Mice: the Nadeau-Taylor Chromosomal Breakage Model RevisitedPavel Pevzner and Glenn TeslerSecond Paper OverviewAre breakpoints random or are some sections of the genome more “fragile” than others?Conventional Wisdom“Since the [random breakage] model was first introduced in [paper cited]..., it has been analyzed by Nadeau and others [more papers cited]... and has become widely accepted”To test, simply plot the lengths of known conserved segments and compare to an exponential distribution...Do we have a match?Too many short segments!Micro-rearrangement Evidence● There is evidence of at least 3,170 micro-rearrangements (reversals) within the synteny blocks (though many may be artifacts of incorrect assemblies)● 41 out of 281 synteny blocks do not show any evidence of micro-rearrangements, while 10 synteny blocks are extremely rearranged (40 or more rearrangements within a block)Calculating Breakpoint ReuseTheorem 1: “If all reversals are delimited by pairs of breakpoints, the number of breakpoint re-uses in any parsimonious reversal scenario is 2d - br. This is the lower bound for non-optimal reversal
View Full Document
Unlocking...