Seqanswers Leaderboard Ad

Collapse

Announcement

Collapse
No announcement yet.
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • de novo assembly with de Bruijn colored graphs

    Hi all!
    I am currently working on an undergrad de novo assembly project to call errors in reads. In his thesis, D. Zerbino mentions that Cortex / Velvet stores variants / errors / alternative samples under new colors. My question is how would we efficiently identify those? I don't really see an optimal implementation for this. Like de Bruijn graphs are fine to construct and traverse if the reads are ideal, but whenever you have a small difference in base pairs, it starts being more complex.
    Any thoughts welcome , thanks!
    Last edited by ArtificialBreeze; 06-15-2015, 12:15 PM.

  • #2
    Just store kmers and counts, and look for branches. When you have a kmer X, there are 4 possible next kmers. Assuming Y is the last K-1 bases of X. Then the 4 possible next kmers are:
    YA
    YC
    YG
    YT

    So, starting from X, just look up the 4 possible next kmers and get their counts. You'll end up with something like this:

    YA 0
    YC 100
    YG 0
    YT 1

    In that case, you have a branch - the next base should be C or T. But T only has a count of 1, so it's probably C; with 101x coverage of a region, it's not unlikely to have 100 correct copies and 1 error.

    However, it also might not be an error (though it probably is). It could be that there are 100 times as many YC kmers in the genome as compared to YT kmers, and both are correct. How you decide whether or not this is an error is up to your heuristics. But regardless, the optimal implementation is generally to store kmer counts in a way they can be quickly looked up (generally by hashing), and only store them for kmers that actually occur.

    If you decide YT is a single substitution error, then for reads containing YT (which in this case would be only 1 read), you would replace the T with a C.
    Last edited by Brian Bushnell; 06-15-2015, 12:20 PM.

    Comment


    • #3
      Oh, I didn't think of that, it is true that this works since we have left and right k-1 mers, which I completely forgot.
      Thanks very much !

      Comment

      Latest Articles

      Collapse

      • seqadmin
        Strategies for Sequencing Challenging Samples
        by seqadmin


        Despite advancements in sequencing platforms and related sample preparation technologies, certain sample types continue to present significant challenges that can compromise sequencing results. Pedro Echave, Senior Manager of the Global Business Segment at Revvity, explained that the success of a sequencing experiment ultimately depends on the amount and integrity of the nucleic acid template (RNA or DNA) obtained from a sample. “The better the quality of the nucleic acid isolated...
        03-22-2024, 06:39 AM
      • seqadmin
        Techniques and Challenges in Conservation Genomics
        by seqadmin



        The field of conservation genomics centers on applying genomics technologies in support of conservation efforts and the preservation of biodiversity. This article features interviews with two researchers who showcase their innovative work and highlight the current state and future of conservation genomics.

        Avian Conservation
        Matthew DeSaix, a recent doctoral graduate from Kristen Ruegg’s lab at The University of Colorado, shared that most of his research...
        03-08-2024, 10:41 AM

      ad_right_rmr

      Collapse

      News

      Collapse

      Topics Statistics Last Post
      Started by seqadmin, Yesterday, 06:37 PM
      0 responses
      11 views
      0 likes
      Last Post seqadmin  
      Started by seqadmin, Yesterday, 06:07 PM
      0 responses
      10 views
      0 likes
      Last Post seqadmin  
      Started by seqadmin, 03-22-2024, 10:03 AM
      0 responses
      51 views
      0 likes
      Last Post seqadmin  
      Started by seqadmin, 03-21-2024, 07:32 AM
      0 responses
      67 views
      0 likes
      Last Post seqadmin  
      Working...
      X