DOC PREVIEW
U of I CS 498 - Greedy Algorithms

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Greedy AlgorithmsGenome RearrangementsSlide 3Comparative Genomic Architectures: Mouse vs Human GenomeA type of rearrangement: ReversalSlide 6BreakpointsTypes of RearrangementsTurnip vs Cabbage: Almost Identical mtDNA gene sequencesTransforming Cabbage into TurnipGenome RearrangementReversals: ExampleSlide 13Reversals and Gene OrdersReversal Distance ProblemSorting By Reversals ProblemSorting By Reversals: A Greedy AlgorithmPowerPoint PresentationGreedy Algorithm: PseudocodeAnalyzing SimpleReversalSortSlide 21Approximation AlgorithmsApproximation Ratio/Performance GuaranteeAdjacencies and BreakpointsBreakpoints: An ExampleAdjacency & BreakpointsReversal Distance and BreakpointsSlide 28Sorting By Reversals: A Better Greedy AlgorithmSlide 30StripsReducing the Number of BreakpointsThings To ConsiderSlide 34Slide 35Slide 36Reducing the Number of Breakpoints (Again)ImprovedBreakpointReversalSortImprovedBreakpointReversalSort: Performance GuaranteeExcursion: UCSC Genome BrowserGreedy AlgorithmsCS 498 SSSaurabh SinhaGenome Rearrangements•Most mouse genes have human orthologs (i.e., share common evolutionary ancestor)•The sequence of genes in the mouse genome is not exactly the same as in human•However, there are subsets of genes with preserved order between human-mouse (“in synteny”)Genome Rearrangements•The mouse genome can be cut into ~300 (not necessarily equal) pieces and joined pasted together in a different order (“rearranged”) to obtain the gene order of the human genome•Synteny blocks•Synteny blocks from different chromosomes in mouse are together on the same chromosome in humanComparative Genomic Architectures: Mouse vs Human Genome•Humans and mice have similar genomes, but their genes are ordered differently•~245 rearrangements–Reversals–Fusions–Fissions–TranslocationA type of rearrangement: Reversal132410568971, 2, 3, 4, 5, 6, 7, 8, 9, 10132410568971, 2, 3, -8, -7, -6, -5, -4, 9, 10A type of rearrangement: Reversal132410568971, 2, 3, -8, -7, -6, -5, -4, 9, 10The reversal introduced two breakpointsBreakpointsTypes 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 6FusionFissionTurnip 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 evolutionTransforming Cabbage into TurnipGenome Rearrangement•Consider reversals only.–These are most common•How to transform one genome (i.e., gene ordering) to another, using the least number of reversals ?Reversals: Example  = 1 2 3 4 5 6 7 8 (3,5) 1 2 5 4 3 6 7 8Reversals: Example  = 1 2 3 4 5 6 7 8 (3,5) 1 2 5 4 3 6 7 8 (5,6)1 2 5 4 6 3 7 8Reversals and Gene Orders•Gene order is represented by a 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 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 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 minimumSorting By Reversals: A Greedy Algorithm•If sorting permutation  = 1 2 3 6 4 5, the first three elements are already in order so it does not make any sense to break them. •The length of the already sorted prefix of  is denoted prefix()– prefix() = 3•This results in an idea for a greedy algorithm: increase prefix() at every step•Doing so,  can be sorted 1 2 3 6 4 5 1 2 3 4 6 5 1 2 3 4 5 6•Number of steps to sort permutation of length n is at most (n – 1)Greedy Algorithm: An ExampleGreedy Algorithm: PseudocodeSimpleReversalSort()1 for i  1 to n – 12 j  position of element i in  (i.e., j = i)3 if j ≠i•   * (i, j)• output 6 if  is the identity permutation 7 returnAnalyzing SimpleReversalSort•SimpleReversalSort does not guarantee the smallest number of reversals and takes five steps on  = 6 1 2 3 4 5 :•Step 1: 1 6 2 3 4 5•Step 2: 1 2 6 3 4 5 •Step 3: 1 2 3 6 4 5•Step 4: 1 2 3 4 6 5•Step 5: 1 2 3 4 5 6•But it can be sorted in two steps: = 6 1 2 3 4 5 –Step 1: 5 4 3 2 1 6 –Step 2: 1 2 3 4 5 6•So, SimpleReversalSort() is not optimal•Optimal algorithms are unknown for many problems; approximation algorithms are usedAnalyzing SimpleReversalSort (cont’d)Approximation Algorithms•These algorithms find approximate solutions rather than optimal solutions•The approximation ratio of an algorithm A on input  is: A() / OPT()where A() -solution produced by algorithm A OPT() - optimal solution of the problemApproximation Ratio/Performance Guarantee•Approximation ratio (performance guarantee) of algorithm A: max approximation ratio of all inputs of size n•For algorithm A that minimizes objective function (minimization algorithm):•max|| = n A() / OPT()•For maximization algorithm:•min|| = n A() / OPT(  = 123…n-1n•A pair of elements  i and  i + 1 are adjacent if i+1 = i + 1•For example:  = 1 9 3 4 7 8 2 6 5•(3, 4) or (7, 8) and (6,5) are adjacent pairsAdjacencies and BreakpointsThere is a breakpoint between


View Full Document

U of I CS 498 - Greedy Algorithms

Documents in this Course
Lecture 5

Lecture 5

13 pages

LECTURE

LECTURE

39 pages

Assurance

Assurance

44 pages

LECTURE

LECTURE

36 pages

Pthreads

Pthreads

29 pages

Load more
Download Greedy Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Greedy Algorithms 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 Greedy Algorithms 2 2 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?