Greedy AlgorithmsCS 498 SSSaurabh SinhaGenome Rearrangements• Most mouse genes have human orthologs(i.e., share common evolutionary ancestor)• The sequence of genes in the mouse genomeis not exactly the same as in human• However, there are subsets of genes withpreserved order between human-mouse (“insynteny”)Genome Rearrangements• The mouse genome can be cut into ~300 (notnecessarily equal) pieces and joined pastedtogether in a different order (“rearranged”) toobtain the gene order of the human genome• Synteny blocks• Synteny blocks from different chromosomesin mouse are together on the samechromosome in humanComparative Genomic Architectures:Mouse vs Human Genome• Humans and micehave similar genomes,but their genes areordered 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 344 5 61 2 64 5 31 2 3 4 5 61 2 3 4 5 6FusionFissionTurnip vs Cabbage: Almost IdenticalmtDNA gene sequences• In 1980s Jeffrey Palmer studied evolution ofplant organelles by comparing mitochondrialgenomes of the cabbage and turnip• 99% similarity between genes• These surprisingly identical gene sequencesdiffered in gene order• This study helped pave the way to analyzinggenome rearrangements in molecularevolutionTransforming Cabbage intoTurnipGenome Rearrangement• Consider reversals only.– These are most common• How to transform one genome (i.e.,gene ordering) to another, using theleast number of reversals ?Reversals: Example π = 1 2 3 4 5 6 7 8 ρ(3,5) 1 2 5 4 3 6 7 8Reversals: 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) theelements from i to j in πρ(ι,j)Reversal Distance Problem• Goal: Given two permutations, find the shortest series ofreversals that transforms one into another• Input: Permutations π and σ• Output: A series of reversals ρ1,…ρt transforming π into σ, suchthat t is minimum• t - reversal distance between π and σSorting By Reversals Problem• Goal: Given a permutation, find a shortest seriesof reversals that transforms it into the identitypermutation (1 2 … n )• Input: Permutation π• Output: A series of reversals ρ1, … ρttransforming π into the identity permutation suchthat t is minimumSorting By Reversals: A Greedy Algorithm• If sorting permutation π = 1 2 3 6 4 5, thefirst three elements are already in order soit 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 greedyalgorithm: increase prefix(π) at every step• Doing so, π can be sorted1 2 3 6 4 5 1 2 3 4 6 5 1 2 3 4 5 6• Number of steps to sort permutation of lengthn is at most (n – 1)GreedyAlgorithm:AnExampleGreedy Algorithm:PseudocodeSimpleReversalSort(π)1 for i 1 to n – 12 j position of element i in π (i.e., πj = i)3 if j ≠i4 π π * ρ(i, j)5 output π6 if π is the identity permutation7 returnAnalyzing SimpleReversalSort• SimpleReversalSort does not guaranteethe smallest number of reversals andtakes 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 manyproblems; approximation algorithms are usedAnalyzingSimpleReversalSort(contʼd)Approximation Algorithms• These algorithms find approximate solutionsrather than optimal solutions• The approximation ratio of an algorithm A oninput π is: A(π) / OPT(π)where A(π) -solution produced by algorithm AOPT(π) - optimal solution of the problemApproximation Ratio/PerformanceGuarantee• Approximation ratio (performanceguarantee) of algorithm A: maxapproximation ratio of all inputs of size n• For algorithm A that minimizes objectivefunction (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 areadjacent 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 adjacentpairsAdjacencies and BreakpointsThere is a breakpoint between any pair of adjacentelements that are non-consecutive: π = 1 9 3 4 7 8 2 6 5• Pairs (1,9), (9,3), (4,7), (8,2) and (2,6) formbreakpoints of permutation π• b(π) - # breakpoints in permutation πBreakpoints: An ExampleAdjacency & Breakpoints•An adjacency - a pair of adjacent elements that are consecutive• A breakpoint - a pair of adjacent elements that are not consecutiveπ = 5 6 2 1 3 40 5 6 2 1 3 4 7adjacenciesbreakpointsExtend π with π0 = 0 and π7 = 7 Each reversal eliminates at most 2 breakpoints.π = 2 3 1 4 6 50 2 3 1 4 6 5 7 b(π) = 50 1 3 2 4 6 5 7 b(π) = 40 1 2 3 4 6 5 7 b(π) = 20 1 2 3 4 5 6 7 b(π) = 0Reversal Distance andBreakpoints Each reversal eliminates at most 2 breakpoints.π = 2 3 1 4 6 50 2 3 1 4 6 5 7 b(π) = 50 1 3 2 4 6 5 7 b(π) = 40 1 2 3 4 6 5 7 b(π) = 20 1 2 3 4 5 6 7 b(π) = 0Reversal Distance andBreakpointsreversal distance ≥ #breakpoints / 2Sorting By Reversals: A Better GreedyAlgorithmBreakPointReversalSort(π)1 while b(π) > 02 Among all possible reversals,choose reversal ρ minimizing b(π • ρ)3 π π • ρ(i, j)4 output π5 returnSorting By Reversals: A Better GreedyAlgorithmBreakPointReversalSort(π)1 while b(π) > 02 Among all possible reversals,choose reversal ρ minimizing b(π • ρ)3 π π • ρ(i, j)4 output π5 returnWhy is this algorithm better than SimpleReversalSort ?Does this
View Full Document
Unlocking...