生物信息学导论 An Introduction to Bioinformatics（PPT讲稿）Exhaustive Search and Branch-and-Bound Algorithms for Partial Digest Mapping

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Exhaustive Search and Branch-and-Bound Algorithms for Partial Digest Mapping

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Exhaustive Search and Branch-and-Bound Algorithms for Partial Digest Mapping

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Molecular scissors EcoRI GHAATT C CTTAAIG Cleavage EcoRI Sticky ends 5 G AATT C 3 彐 CTTAA 5 Molecular Cell Biology edition

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Molecular Scissors Molecular Cell Biology, 4th edition

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Recognition Sites of Restriction Enzymes Enzyme Source microorganism Recugnition Site Ends produces Baml Il Bacillus auryioligsefuciens -G-G-A-T-C-( Sticky (.(T-A(( 上cll Escherich coli GAATIC CTIAAG HindIll H若 aphis infima.e A- A-G-CI-I I-T-C-G.A-A- Kail (-(TA-(.C -C-C-A-T-C( Molecular Cell Biology edition

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Recognition Sites of Restriction Enzymes Molecular Cell Biology, 4th edition

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Uses of Restriction Enzymes Recombinant DNA technology Cloning CDNA/genomic library construction DNA mapping

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Uses of Restriction Enzymes • Recombinant DNA technology • Cloning • cDNA/genomic library construction • DNA mapping

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Restriction Maps A map showing positions of restriction sites in a DNA sequence Ec001092674 BstAP 179 If dNa sequence is Aatll 2617 Ndel 183 Sspl 2501 known then construction The 235 Pdml 2294 of restriction map is a BcgI 2215 MCS trivial exercise Scal 2177 In early days of molecular biology dNA sequences were often pUC18/19 Sapl 683 2686bp unknown Biologists had to solve Af/l, BspLU111 806 Gsul 1784 the problem of 1626 c011779 constructing restriction Ec0311766 Eam1105l1694 maps without knowing DNA sequences A Call 1217

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Restriction 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 sequences

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Gel Electrophoresis: Example kb 20 10 Direction of dna movement Smaller fragments travel farther b c a bc b c Molecular Cell Biology edition

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Gel Electrophoresis: Example Direction of DNA movement Smaller fragments travel farther Molecular Cell Biology, 4th edition

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Partial 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 sequence

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Partial 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 sequence

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Partial Digest EXample Partial Digest results in the following 10 restriction fragments Restriction Sites

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Partial Digest Example • Partial Digest results in the following 10 restriction fragments:

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Multiset of Restriction Fragments We assume Restriction Sites that multiplicity of a fragment can be detected L.e.. the number of restriction fragments of the same length can be determined (e.g, by observing twice as much fluorescence intensity for a double fragment than for a single fragment Multiset:{3,5,5,8,9,14,14,17,19,22}

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Multiset of Restriction Fragments • We assume that multiplicity of a fragment can be detected, i.e., the number of restriction fragments of the same length can be determined (e.g., by observing twice as much fluorescence intensity for a double fragment than for a single fragment) Multiset: {3, 5, 5, 8, 9, 14, 14, 17, 19, 22}

An Introduction to Bioinformatics algorithms www.bioalgorithms.info Partial Digest Fundamentals X: the set of n integers representing the location of all cuts in the restriction map including the start and end n: the total number of cuts DX the multiset of integers representing lengths of each of the C(n, 2)fragments produced from a partial digest

An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Partial Digest Fundamentals the set of n integers representing the location of all cuts in the restriction map, including the start and end the multiset of integers representing lengths of each of the C(n,2) fragments produced from a partial digest the total number of cuts X: n: DX: