Banana Slug Genomics

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Lecture Notes for April 09, 2010 ======

Add to these lecture notes with any notes you have!

===== Notes before main lecture =====

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.
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.

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 comparable between the platforms and runs

It can be informative, once reads are mapped, to look at the quality scores for reads with observed errors.

//Pog// assembly is down to only 8 snps & one potentially variable insert

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 =====

Types of assembler graphs:
  * Overlap graph
  * de Bruijn graph  (pronounced like "De Broin")

Differences are "What are the nodes?"
  * Overlap: reads
  * de Bruijn: k-mers (usually fixed k, k < = length(read))

=== Overlap graphs ===

* read -> * read (a directed graph)
<code>
        A
_______________
    | | | | | |
    __________________
            B
</code>
The problem with edges between contig nodes is in defining direction of the reads when aligning:
  * 4 different edge scenarios:
    * -> -> (A -> B)
    * -> <- (A -> B' or B -> A')
    * <- -> (B' -> A or A' -> B)
    * <- <- (B -> A)
  * 3 different edge types:
    * same dir: A to B / B to A
    * tail-to-tail (convergent): 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)


=== de Bruijn graphs ===

* kmer -> * kmer -> * kmer -> * kmer …

<code>
|----------|
 |-----------|
  |----------|
   |----------|
    …
</code>

No different than a count of k+1 mers.

Ways to handle representing the graph:
  * Direct addressing (becomes useless for assembly, need to map to unique places)
  * Hashing (key = size of kmer, have to go to 20…25 mer for the keys to start to be unique)

 May run into problems with RAM on the computational nodes. 
  * ~ 16 GB per core, was that 4 cores sharing 16 GB or each core with 16 GB?
  * /proc/meminfo, /proc/cpuinfo directories contains information about the node

With overlap graph:

A -> B

A -> C

A -> D

<code>
|----------| A
    |----------| B
    |----------| C
       |----------| D
</code>

Don't know where to go / which copy of the repeat currently in.

In ideal situation for de Bruijn graph:

<code>
kmer -> kmer -> kmer -> kmer -> kmer (done!)
</code>

Realistically, there are issues:

End of Contig boundaries:
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>
kmer -> kmer -> kmer -> kmer -> kmer
    \-> kmer -> kmer -> kmer (off to nowhere)
</code>
path diverges but does not reconverge, resulting in source/sink dead-ends (these are likely due to read errors)

Bubbles:
<code>
    /-> kmer -> kmer -> kmer -\
kmer -> kmer -> kmer -> kmer -> kmer
</code>

 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

Other issues:

Loop:
<code>
kmer -> kmer -> kmer -> kmer -> kmer -> kmer -> kmer
                            \- kmers <-/
</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

Multiple paths:
<code>
A                      B
 \                    /
  ------------------->
 /                    \
B                      A'
</code>

Which path to take?

If you have clean data, you can disambiguate some issues.
Largest bias usually comes from PCR for amplification.


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
Banana Slug Genomics

User Tools

Site Tools

Page Tools
