Slide 1Next-Generation SequencingProblem StatementWorkflowIndexing the genomeBuilding the Hash TableAlignmentAverage Read ProbabilitySingle Read VariationProbabilistic Needleman WunschAssignmentAssignmentEquation for probabilistic mappingWhich Program to Use?Simulation StudiesSimulation StudiesActual DataFuture PlansAcknowledgementsSlide 20GNUMap: Unbiased Probabilistic Mapping of Next-Generation Sequencing ReadsNathan ClementComputational Sciences LaboratoryBrigham Young UniversityProvo, Utah, USAComputational Sciences LaboratoryBrigham Young UniversityNext-Generation SequencingComputational Sciences LaboratoryBrigham Young UniversityProblem Statement•Map next-generation sequence reads with variable nucleotide confidence to a model reference genome that may be different from the subject genome.▫SpeedTens of millions of reads to a 3Gbp genome▫AccuracyMismatches included?Repetitive regions▫VisualizationComputational Sciences LaboratoryBrigham Young UniversityWorkflowComputational Sciences LaboratoryBrigham Young UniversityIndexing the genome•Fast lookup of possible hit locations for the reads▫Hashing groups locations in the genome that have similar sequence contentk-mer hash of exact matches in genome can be used to narrow down possible match locations for reads▫Sorting genome locations provides for content addressing of genome•GNUMap uses indexing of all 10-mers in the genome as seed points for read mappingComputational Sciences LaboratoryBrigham Young UniversityBuilding the Hash TableACTGAACCATACGGGTACTGAACCATGAATGGCACCTATACGAGATACGCCATACACTGAACCATACGGGTACTGAACCATGAATGGCACCTATACGAGATACGCCATACHash TableAACCATAACCATAACCATAACCATSliding window indexes all locations in the genomeComputational Sciences LaboratoryBrigham Young UniversityAlignment•Given a possible genome match location, determine the quality of the match•If you call bases in the read▫Every base gets the same weight in the alignment, no matter what the quality▫Later bases in the read that have lower quality have equal weight in the alignment with high quality bases at the start of the read•GNUMap uses a Probabilistic Needleman-Wunsch to align reads found with seed points from the genome hashComputational Sciences LaboratoryBrigham Young UniversityAverage Read ProbabilityComputational Sciences LaboratoryBrigham Young UniversitySingle Read VariationComputational Sciences LaboratoryBrigham Young UniversityProbabilistic Needleman Wunsch•Allows for probabilistic mismatches and gaps•Greater ability to map reads of variable confidence•Produces likelihood of alignmentComputational Sciences LaboratoryBrigham Young UniversityAssignment•Given a read that has matches to possibly multiple locations in the genome, assign the read to locations where it matches▫Discard read – Repeat masking repetitive regions Half of the human genome contains repeat regions, so you are not able to map to those regionsMany regulatory regions are repeated in the genome▫Map to all locations – Repeat regions will be over-represented since one read will generate multiple hits▫Pick a random location – Highly variable if there are small numbers of reads•GNUMap uses probabilistic mapping to allocate a share of the read to matching locations in the genome according to the quality of the matchComputational Sciences LaboratoryBrigham Young UniversityAssignmentACTGAACCATACGGGTACTGAACCATGAAACTGAACCATACGGGTACTGAACCATGAAAACCATAACCATGGGTACAACCATTACGGGTACAACCATTACRead from sequencerGGGTACGGGTACAACCATAACCATRead is added to both repeat regions proportionally to their match qualityComputational Sciences LaboratoryBrigham Young UniversityEquation for probabilistic mapping•Posterior Probability•Allows for multiple sequences of different matching quality•Includes probability of each read coming from any genomic position€ Gj=QjQj+ Qkk≠ jn∑Computational Sciences LaboratoryBrigham Young UniversityWhich Program to Use?•Many different programs. How do they relate?▫ELAND (included with Solexa 1G machine)▫RMAP (Smith et al., BMC Bioinformatics 2008)▫SOAP (Li et al., Bioinformatics 2008)▫SeqMap (Jiang et al., Bioinformatics 2008)▫Slider (Malhis et al., Bioinformatics 2008)▫MAQ (Unpublished, http://maq.sourceforge.net/)▫Novocraft (Unpublished, http://www.novocraft.com)▫Zoom (Lin et al., Bioinformatics 2008)▫Bowtie (Langmead et al., Genome Biology 2009)▫…Computational Sciences LaboratoryBrigham Young UniversitySimulation Studies•Ambiguous reads cause:1. Missed (unmapped) regions2. Too many mapped regions (noise)Computational Sciences LaboratoryBrigham Young UniversitySimulation StudiesComputational Sciences LaboratoryBrigham Young UniversityActual Data•ETS1 binding domain•Repetitive regionComputational Sciences LaboratoryBrigham Young UniversityFuture Plans•Removal of adaptor sequences•Methylation analysis•Paired-end reads•SOLiD color spaceAcknowledgementsEvan JohnsonQuinn SnellMark ClementHuntsman Cancer Institutehttp://dna.cs.byu.edu/gnumapComputational Sciences LaboratoryBrigham Young
View Full Document
Unlocking...