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 <14> <19> <9> <14> <3>
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 <5> of restriction <14> fragments of <19> the same length can be determined (e.g, by <14> observing twice as much <17> 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: