User Tools

Site Tools


lecture_notes:04-09-2010

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last revision Both sides next revision
lecture_notes:04-09-2010 [2010/04/09 22:01]
cbrumbau Fixed less than or equal to symbol
lecture_notes:04-09-2010 [2010/04/11 15:32]
learithe
Line 7: Line 7:
 Take fix mode script from /​projects/​compbio/​bin/​scripts and replace protein user group with BME 235 user group. Take fix mode script from /​projects/​compbio/​bin/​scripts and replace protein user group with BME 235 user group.
  
-Next week will have a reference genome (POG) to use for testing the tools on. +Next week will have a reference genome (//​Pyrobaculum oguniense//,​ aka //"​Pog"//​) to use for testing the tools on. 
-For the most part POG is done; however, there are still some uncertainty with 8 SNPs left. It is definitely past the MIAMI standard at this point.+For the most part Pog is done; however, there are still some uncertainty with 8 SNPs left. It is definitely past the MIAMI standard at this point. (//Pog// assembly is down to only 8 snps & one potentially variable insert) 
 + 
 +Note about sequencing platform quality scores: most platforms are trying to use the phred quality score((http://​en.wikipedia.org/​wiki/​Phred_quality_score)),​ so the quality score is theoretically comparable between the platforms and runs (although calibration causes scores to vary between runs and instruments nonetheless) 
 + 
 +It can be informative,​ once reads are mapped, to look at the quality scores for reads with observed errors. 
 + 
 + 
 + 
 +Lior Pachter (from UC Berkeley) is vising on Monday, to speak about the Bowtie/​TopHat/​CuffLinks algorithms. Bowtie: mapping; TopHat/​Cufflinks:​ find splice junctions, predicted spliced transcripts. Bowtie is used in a lot of the assembly agorithms.
  
 ===== Main lecture: Assembler graphs ===== ===== Main lecture: Assembler graphs =====
Line 14: Line 22:
 Types of assembler graphs: Types of assembler graphs:
   * Overlap graph   * Overlap graph
-  * de Bruijn graph+  * de Bruijn graph  ​(pronounced like "De Broin"​)
  
 Differences are "What are the nodes?"​ Differences are "What are the nodes?"​
Line 30: Line 38:
             B             B
 </​code>​ </​code>​
-The problem is the direction of the reads when aligning:+The problem ​with edges between contig nodes is in defining ​direction of the reads when aligning:
   * 4 different edge scenarios:   * 4 different edge scenarios:
     * -> -> (A -> B)     * -> -> (A -> B)
Line 37: Line 45:
     * <- <- (B -> A)     * <- <- (B -> A)
   * 3 different edge types:   * 3 different edge types:
-    * A to B +    * same dir: A to B B to A 
-    * B to A +    * tail-to-tail (convergent): ​A' to B  
-    * A' to B A to B'+    * head-to-head (divergent): ​A to B' 
 + 
 +Need to have some tolerance for error because the reads are noisy. When creating read overlaps, if you require 100% pairing, you’ll miss a lot of data. plus these include the read ends, where quality falls off. so need a “overlap quality score”. 
 + 
 +Can’t do all-vs-all searches (n^2 algorithms not a good idea with billions of reads…). So how do you search what to overlap? Most algorithms do a blast-like filter before trying to align edges (~ nlogn) 
 + 
 + 
 +(Side Note: for transcriptome libraries, if done properly, reads should have known strandedness,​ so can’t be run through algorithms which make strandedness arbitrary (story about problems with a prominent yeast microarray transcriptome analysis incorrectly finding a lot of “antisense” mRNAs due to library prep error)
  
-Need to have some tolerance for error because the reads are noisy. 
  
 === de Bruijn graphs === === de Bruijn graphs ===
Line 89: Line 103:
  
 Realistically,​ there are issues: Realistically,​ there are issues:
 +== End of Contig boundaries: ==
  
-Spurs:+what if A->B and A->C and A->D BUT A->B and A->C are inconsistent with each other? 
 +… A becomes “end of contig”, because you aren’t sure where to go next 
 +also end of contig if there are no more edges from the node 
 + 
 +== Spurs: ​==
 <​code>​ <​code>​
 kmer -> kmer -> kmer -> kmer -> kmer kmer -> kmer -> kmer -> kmer -> kmer
     \-> kmer -> kmer -> kmer (off to nowhere)     \-> kmer -> kmer -> kmer (off to nowhere)
 </​code>​ </​code>​
 +path diverges but does not reconverge, resulting in source/sink dead-ends (these are likely due to read errors)
  
-Collapse bubbles:+== Bubbles==
 <​code>​ <​code>​
     /-> kmer -> kmer -> kmer -\     /-> kmer -> kmer -> kmer -\
Line 102: Line 122:
 </​code>​ </​code>​
  
-Other issues:+ path splits due to a SNP but then converges. this can happen with real SNPs, read error SNPs, and real repeats which differ by a SNP or two
  
-Loop:+== Loop: ==
 <​code>​ <​code>​
 kmer -> kmer -> kmer -> kmer -> kmer -> kmer -> kmer kmer -> kmer -> kmer -> kmer -> kmer -> kmer -> kmer
                             \- kmers <-/                             \- kmers <-/
 </​code>​ </​code>​
 +tandem repeats will generate a circle, but have edges in and out; hard to disambiguate copy # though. If the data is really clean (ie, in/out edges are ~10 read-depth with low SD, and inside circle has ~20 read-depth with low SD), can guess that there might be 2 copies of the repeat, but not highly reliable
  
-Take the loop? +== Multiple paths: ​==
- +
-Multiple paths:+
 <​code>​ <​code>​
 A                      B A                      B
Line 126: Line 145:
 Largest bias usually comes from PCR for amplification. Largest bias usually comes from PCR for amplification.
  
-Need to collapse the graph (both overlap and de Bruijn) to assemble the reads.+===Assembly:​=== 
 +algorithms ​(both overlap and de Bruijn) ​need to collapse bubbles and trim spurs.\\ 
 +spurs: discard if their read count is low\\ 
 +bubbles: tricky, because they can represent real, divergent paths 
 + 
 + 
lecture_notes/04-09-2010.txt · Last modified: 2010/04/12 14:37 by cbrumbau