Exhaustive searchAgendaRestriction MappingRestriction enzymesMolecular ScissorsRecognition Sites of Restriction EnzymesRestriction MapsMeasuring Length of Restriction FragmentsPartial Restriction DigestSlide 10Partial Digest Problem (PDP)Brute force algorithmBrute Force PDPBrute Force PDP 2A practical solution: key ideaSlide 16Slide 17NotationAn ExampleSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34AlgorithmTime complexityMotif findingMy fruitfly has a bacterial infectionLooking for differentially expressed genesDNA Arrays--Technical FoundationsDNA MicroarrayAn experiment on a microarrayDifferentially expressed genesRegulatory motifFinding motifs ab initioSimple statisticsVariation in binding sitesA new motif modelMotifs: Profiles and ConsensusProfile matricesScoring MotifsGood profile matricesToday’s summaryExhaustive searchCs 498 SSSaurabh SinhaAgenda•Two different problems–Restriction mapping–Motif finding–Common theme: exhaustive search of solution space•Reading: Chapter 4.Restriction MappingRestriction enzymes•A protein that cuts DNA at very specific sites (occurrences of a particular word)•Foreign DNA entering a bacterium is usually unable to do anything•Reason: Restriction enzymes shred the DNA •Do not cleave “methylated” DNA–Host DNA is suitably methylated, hence protectedMolecular ScissorsMolecular Cell Biology, 4th editionRecognition Sites of Restriction EnzymesMolecular Cell Biology, 4th editionRestriction Maps• A map showing positions of restriction sites in a DNA sequence• If DNA sequence is known then construction of restriction map is a trivial exercise• In early days of molecular biology DNA sequences were often unknown• Biologists had to solve the problem of constructing restriction maps without knowing DNA sequencesMeasuring Length of Restriction Fragments•Restriction enzymes break DNA into restriction fragments. •Gel electrophoresis is a process for separating DNA by size and measuring sizes of restriction fragments •Can separate DNA fragments that differ in length in only 1 nucleotide for fragments up to 500 nucleotides longPartial Restriction Digest•The sample of DNA is exposed to the restriction enzyme for only a limited amount of time to prevent it from being cut at all restriction sites•This experiment generates the set of all possible restriction fragments between every two (not necessarily consecutive) cuts•This set of fragment sizes is used to determine the positions of the restriction sites in the DNA sequencePartial Restriction DigestMultiset of fragment lengths: {3, 5, 5, 8, 9, 14, 14, 17, 19, 22}Partial Digest Problem (PDP)•Let X = { x1 = 0, x2, x3, … xn }•Given pairwise distances between each pair {xi, xj} •∆X = { xj - xi | 1 ≤ i < j ≤ n }•Reconstruct X•Does a unique solution exist ?Brute force algorithm•Also called enumerative algorithms•Used in some problems in bioinformatics•If the program runs in reasonable time …•If the “goodness” of the algorithm is in a special objective function, enumerative search can guarantee finding the optimal solutionBrute Force PDP•Given L = set of all pairwise distances•Need to find X such that ∆X = L•Know that x1 = 0 and xn = M (where M is the largest number in L)•x2, x3, … xn-1 must all be integers between 1 and M-1. •Try all possible solutions: •Approximately O(Mn-2)Brute Force PDP 2•Do we need to try every integer between 0 and M ?•Since x1 = 0, for every xi in X, the number (xi - x1) = xi must be in ∆X•We need to find X such that ∆X = L. Therefore, only consider xi that are in L•Therefore, only |L| possibilities from which to choose n-2 numbers•Try all possible solutions:•Approximately O(|L|n-2), i.e., O(n2n-4)A practical solution: key idea0MPick the largest (other than M) number from LLet this be ∂A practical solution: key idea0MCase i∂∂A practical solution: key idea0MCase iiM-∂∂NotationD(y, X) = {|y – x1|, |y – x2|, …, |y – xn|} for X = {x1, x2, …, xn}An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0 }An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0 }Remove 10 from L and insert it into X. We know this must bethe length of the DNA sequence because it is the largestfragment.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 10 }An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 10 }Take 8 from L and make y = 2 or 8. Let us go with y = 2.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 10 }We find that the distances from y=2 to other elements in X are D(y, X) = {8, 2}, so we remove {8, 2} from L and add 2 to X.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 10 }An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 10 }Take 7 from L and make y = 7 or y = 10 – 7 = 3. We willexplore y = 7 first, so D(y, X ) = {7, 5, 3}.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 10 }For y = 7 first, D(y, X ) = {7, 5, 3}. Therefore we remove {7, 5 ,3} from L and add 7 to X.D(y, X) = {7, 5, 3}An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 7, 10 }An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 7, 10 }Take 6 from L and make y = 6. Unfortunately D(y, X) = {6, 4, 1 ,4}, which is not a subset of L. Therefore we won’t explore this branch.6An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 7, 10 }This time make y = 4. D(y, X) = {4, 2, 3 ,6}, which is a subset of L so we will explore this branch. We remove {4, 2, 3 ,6} from L and add 4 to X.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 4, 7, 10 }An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 4, 7, 10 }L is now empty, so we have a solution, which is X.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 7, 10 }To find other solutions, we backtrack.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 10 }More backtrack.An ExampleL = { 2, 2, 3, 3, 4, 5, 6, 7, 8, 10 }X = { 0, 2, 10 }This time we will explore y = 3. D(y, X) = {3, 1, 7}, which isnot a subset of L, so we won’t explore this branch.Algorithm•Given L, build X incrementally, starting from X = {0, M}•At each step, extract y = maximum element in L•Consider the two possibilities: • y is in X•M - y is in X•Check if either possibility is consistent with L, and if so, include that in X, remove the induced pairwise distances from L, and
View Full Document
Unlocking...