DNA SequencingDNA Sequencing – gel electrophoresisElectrophoresis diagramsMethod to sequence longer regionsSlide 5Definition of CoverageRepeatsSequencing and Fragment AssemblyWhat can we do about repeats?Slide 10Slide 11Slide 12Slide 13Strategies for whole-genome sequencingHierarchical SequencingHierarchical Sequencing StrategyMethods of physical mapping1. HybridizationHybridization – Computational ChallengeSlide 20Slide 212. DigestionOnline Clone-by-clone The Walking MethodThe Walking MethodSlide 25Walking off a Single SeedSlide 28Walking off several seeds in parallelSlide 31Whole Genome Shotgun SequencingFragment Assembly (in whole-genome shotgun sequencing)Fragment AssemblySteps to Assemble a Genome1. Find Overlapping ReadsSlide 37Slide 38Slide 392. Merge Reads into ContigsSlide 41Slide 42Slide 43Slide 44Slide 45Overlap graph after forming contigsRepeats, errors, and contig lengthsSlide 48Slide 49Slide 50Slide 514. Derive Consensus SequenceSome AssemblersQuality of assembliesQuality of assemblies—mouseQuality of assemblies—mouseQuality of assemblies—ratHistory of WGAGenomes SequencedDNA SequencingCS262 Lecture 9, Win06, BatzoglouDNA Sequencing – gel electrophoresis1. Start at primer (restriction site)2. Grow DNA chain3. Include dideoxynucleoside (modified a, c, g, t)4. Stops reaction at all possible points5. Separate products with length, using gel electrophoresisCS262 Lecture 9, Win06, BatzoglouElectrophoresis diagramsCS262 Lecture 9, Win06, BatzoglouMethod to sequence longer regionscut many times at random (Shotgun)genomic segmentGet one or two reads from each segment~500 bp ~500 bpCS262 Lecture 9, Win06, BatzoglouReconstructing the Sequence (Fragment Assembly)Cover region with ~7-fold redundancy (7X)Overlap reads and extend to reconstruct the original genomic regionreadsCS262 Lecture 9, Win06, BatzoglouDefinition of CoverageLength of genomic segment: LNumber of reads: nLength of each read: lDefinition: Coverage C = n l / LHow much coverage is enough?Lander-Waterman model:Assuming uniform distribution of reads, C=10 results in 1 gapped region /1,000,000 nucleotidesCCS262 Lecture 9, Win06, BatzoglouRepeatsBacterial genomes: 5%Mammals: 50%Repeat types:•Low-Complexity DNA (e.g. ATATATATACATA…)•Microsatellite repeats (a1…ak)N where k ~ 3-6(e.g. CAGCAGTAGCAGCACCAG)•Transposons SINE (Short Interspersed Nuclear Elements)e.g., ALU: ~300-long, 106 copiesLINE (Long Interspersed Nuclear Elements)~4000-long, 200,000 copiesLTR retroposons (Long Terminal Repeats (~700 bp) at each end)cousins of HIV•Gene Families genes duplicate & then diverge (paralogs)•Recent duplications ~100,000-long, very similar copiesCS262 Lecture 9, Win06, BatzoglouSequencing and Fragment AssemblyAGTAGCACAGACTACGACGAGACGATCGTGCGAGCGACGGCGTAGTGTGCTGTACTGTCGTGTGTGTGTACTCTCCT3x109 nucleotides50% of human DNA is composed of repeatsError!Glued together two distant regionsCS262 Lecture 9, Win06, BatzoglouWhat can we do about repeats?Two main approaches:•Cluster the reads•Link the readsCS262 Lecture 9, Win06, BatzoglouWhat can we do about repeats?Two main approaches:•Cluster the reads•Link the readsCS262 Lecture 9, Win06, BatzoglouWhat can we do about repeats?Two main approaches:•Cluster the reads•Link the readsCS262 Lecture 9, Win06, BatzoglouSequencing and Fragment AssemblyAGTAGCACAGACTACGACGAGACGATCGTGCGAGCGACGGCGTAGTGTGCTGTACTGTCGTGTGTGTGTACTCTCCT3x109 nucleotidesCRDARB, CRDorARD, CRB ?A R BCS262 Lecture 9, Win06, BatzoglouSequencing and Fragment AssemblyAGTAGCACAGACTACGACGAGACGATCGTGCGAGCGACGGCGTAGTGTGCTGTACTGTCGTGTGTGTGTACTCTCCT3x109 nucleotidesCS262 Lecture 9, Win06, BatzoglouStrategies for whole-genome sequencing 1. Hierarchical – Clone-by-clonei. Break genome into many long piecesii. Map each long piece onto the genomeiii. Sequence each piece with shotgunExample: Yeast, Worm, Human, Rat2. Online version of (1) – Walkingi. Break genome into many long piecesii. Start sequencing each piece with shotguniii. Construct map as you goExample: Rice genome3. Whole genome shotgunOne large shotgun pass on the whole genomeExample: Drosophila, Human (Celera), Neurospora, Mouse, Rat, DogHierarchical SequencingCS262 Lecture 9, Win06, BatzoglouHierarchical Sequencing Strategy1. Obtain a large collection of BAC clones2. Map them onto the genome (Physical Mapping)3. Select a minimum tiling path4. Sequence each clone in the path with shotgun5. Assemble6. Put everything togethera BAC clonemapgenomeCS262 Lecture 9, Win06, BatzoglouMethods of physical mappingGoal: Make a map of the locations of each clone relative to one another Use the map to select a minimal set of clones to sequenceMethods:•Hybridization•DigestionCS262 Lecture 9, Win06, Batzoglou1. HybridizationShort words, the probes, attach to complementary words1. Construct many probes2. Treat each BAC with all probes3. Record which ones attach to it4. Same words attaching to BACS X, Y overlapp1pnCS262 Lecture 9, Win06, BatzoglouHybridization – Computational ChallengeMatrix:m probes n clones(i, j): 1, if pi hybridizes to Cj0, otherwiseDefinition: Consecutive ones matrix1s are consecutive in each row & colComputational problem:Reorder the probes so that matrix is in consecutive-ones formCan be solved in O(m3) time (m > n)p1 p2 …………………….pmC1 C2 ……………….Cn1 0 1…………………...01 1 0 …………………..00 0 1 …………………..1pi1pi2…………………….pimCj1Cj2 ……………….Cjn1 1 1 0 0 0……………..00 1 1 1 1 1……………..00 0 1 1 1 0……………..00 0 0 0 0 0………1 1 1 00 0 0 0 0 0………0 1 1 1CS262 Lecture 9, Win06, BatzoglouHybridization – Computational ChallengeIf we put the matrix in consecutive-ones form,then we can deduce the order of the clones& which pairs of clones overlappi1pi2…………………….pimCj1Cj2 ……………….Cjn1 1 1 0 0 0……………..00 1 1 1 1 1……………..00 0 1 1 1 0……………..00 0 0 0 0 0………1 1 1 00 0 0 0 0 0………0 1 1 1Cj1Cj2 ……………….Cjnpi1pi2………………………………….pimCS262 Lecture 9, Win06, BatzoglouHybridization – Computational ChallengeAdditional challenge:A probe (short word) can hybridize in many places in the genomeComputational Problem:Find the order of probes that implies the minimal probe repetitionEquivalent: find the shortest string of probes such that each clone appears as a substringAPX-hardSolutions:Greedy, probabilistic,
View Full Document
Unlocking...