Answers.Body: <p>It's common for assemblers to have a coverage threshold to make sure that there are enough reads across the same region to properly assemble a contig.</p>
  
  <p>You can't work out an ideal solution from a situation where the consensus sequence is ambiguous. If your overlap were representative (e.g. a heterozygous variant in a diploid genome, based on a few tens of reads of 100bp, rather than 6bp), then the resulting assembly would have a bubble in the assembly graph at the variant point.</p>
  
  <pre><code>        A
         / \
  A-A-C-T   G-A-T
         \ /
          C
  </code></pre>
  
  <p>A conservative assembler might produce two assembled contigs corresponding to these two paths, AACTAGAT and AACTCGAT. A greedy assembler would just pick one path and use that. Subsequent assembly steps might attempt to search for bubbles and annotate the assembled contigs with variant locations.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-22T21:07:31.287Z
Answers.Text: For all mainstream short-read overlappers, if there is a mismatch, the overlap will be missed entirely. You don't get a bubble. Usually you need at least 4 reads to see a bubble and the bubble is not single-based in string/overlap graph.
Answers.UserDisplayName: user172818
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-23T01:04:49.970Z
Answers.Text: Yes, for the particular example that was given, a bubble wouldn't be formed. I was assuming that the reads were representative of something with a better coverage (e.g. overlap of 50 long sequences, with half having a variant, and half not)
Answers.UserDisplayName: gringer
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-22T18:47:50.417Z
Answers.LastActivityDate: 2017-10-23T01:05:59.507Z
Answers.LastEditDate: 2017-10-23T01:05:59.507Z
Answers.UserDisplayName: gringer
Answers.Body: <p>For short reads, the typical and the most widely used solution is to correct away sequencing errors before assembly. You can correct errors with k-mer spectrum, a trie or multi-alignment. There are many papers on this topic.</p>
  
  <p>Error correction alone won't fix all sequencing errors. Remaining errors may lead to bubbles and tips in the overlap/de Bruijn graph. You can identify them by inspecting the local topology of assembly graph.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-22T17:35:05.253Z
Answers.Text: So what would be solution from error-prone sample above?
Answers.UserDisplayName: gagro
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-22T21:03:39.660Z
Answers.Text: No solution to your example. You can only identify errors with sufficient coverage.
Answers.UserDisplayName: user172818
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-22T14:13:23.250Z
Answers.LastActivityDate: 2017-10-22T14:13:23.250Z
Answers.UserDisplayName: user172818
Body: <p>I understand how to assemble genome from error-free reads. I implemented like this: </p>
  
  <blockquote>
    <p>Construct directed overlap graph with reads as vertices and edges as
    maximum overlap between two vertices. Edges represent the length of
    overlapping maximum substring of one read suffix with other read
    prefix. Find the path that visits all vertices only once in overlap
    graph. With small graph we can use greedy approach : Starting from
    first pattern always choose egde of maximum weight and store shortest
    common superstring spelled by this path in resulting string. Resulting
    string spelled by path is shortest common superstring of all reads,
    that is assembled genome.</p>
  </blockquote>
  
  <p>For example </p>
  
  <pre><code>AACTAG
    CTAGAT
  </code></pre>
  
  <p>Gives the <code>AACTAGAT</code> as a result</p>
  
  <p>Now let's say that two error-prone reads have at most one error (mismatch):</p>
  
  <pre><code>AACTAG
    CTCGAT
  </code></pre>
  
  <p>As you can see second read has one substitution in third character from <strong>'A'</strong> to <strong>'C'</strong>.</p>
  
  <p>So how assembled genome should look like for the error-prone reads? Do I take <strong>A</strong> or <strong>C</strong> to resulting string? Or I'm missing something?</p>
  
  <p>Note: I used short reads for example because of simplicity. I work with much larger number of reads which are 100 nucleotides long and have at most one substitution of character. So that's a big overlap graph. I know I can use De Bruijn graph, but can I use some greedy approach (like in error-free example)?  </p>
  
Tags: <genome><assembly><reads>
Title: Genome assembly from error-prone reads
ThreadText: # Genome assembly from error-prone reads
  
  (Asked by: username_0 on 2017-10-22)
  
  I understand how to assemble genome from error-free reads. I implemented like this:
  
  > Construct directed overlap graph with reads as vertices and edges as
  > maximum overlap between two vertices. Edges represent the length of
  > overlapping maximum substring of one read suffix with other read
  > prefix. Find the path that visits all vertices only once in overlap
  > graph. With small graph we can use greedy approach : Starting from
  > first pattern always choose egde of maximum weight and store shortest
  > common superstring spelled by this path in resulting string. Resulting
  > string spelled by path is shortest common superstring of all reads,
  > that is assembled genome.
  
  For example
  
  ```
  AACTAG
    CTAGAT
  
  ```
  
  Gives the `AACTAGAT` as a result
  
  Now let's say that two error-prone reads have at most one error (mismatch):
  
  ```
  AACTAG
    CTCGAT
  
  ```
  
  As you can see second read has one substitution in third character from **'A'** to **'C'**.
  
  So how assembled genome should look like for the error-prone reads? Do I take **A** or **C** to resulting string? Or I'm missing something?
  
  Note: I used short reads for example because of simplicity. I work with much larger number of reads which are 100 nucleotides long and have at most one substitution of character. So that's a big overlap graph. I know I can use De Bruijn graph, but can I use some greedy approach (like in error-free example)?
  
  **Tags:** genome, assembly, reads
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2017-10-22. Score: 1 | Accepted answer
  
  It's common for assemblers to have a coverage threshold to make sure that there are enough reads across the same region to properly assemble a contig.
  
  You can't work out an ideal solution from a situation where the consensus sequence is ambiguous. If your overlap were representative (e.g. a heterozygous variant in a diploid genome, based on a few tens of reads of 100bp, rather than 6bp), then the resulting assembly would have a bubble in the assembly graph at the variant point.
  
  ```
          A
         / \
  A-A-C-T   G-A-T
         \ /
          C
  
  ```
  
  A conservative assembler might produce two assembled contigs corresponding to these two paths, AACTAGAT and AACTCGAT. A greedy assembler would just pick one path and use that. Subsequent assembly steps might attempt to search for bubbles and annotate the assembled contigs with variant locations.
  
  > **Comments:**
  > **username_2**: For all mainstream short-read overlappers, if there is a mismatch, the overlap will be missed entirely. You don't get a bubble. Usually you need at least 4 reads to see a bubble and the bubble is not single-based in string/overlap graph.  
  > **username_1**: Yes, for the particular example that was given, a bubble wouldn't be formed. I was assuming that the reads were representative of something with a better coverage (e.g. overlap of 50 long sequences, with half having a variant, and half not)  
  
  ---
  
  ### Answer by username_2 on 2017-10-22. Score: 2
  
  For short reads, the typical and the most widely used solution is to correct away sequencing errors before assembly. You can correct errors with k-mer spectrum, a trie or multi-alignment. There are many papers on this topic.
  
  Error correction alone won't fix all sequencing errors. Remaining errors may lead to bubbles and tips in the overlap/de Bruijn graph. You can identify them by inspecting the local topology of assembly graph.
  
  > **Comments:**
  > **username_0**: So what would be solution from error-prone sample above?  
  > **username_2**: No solution to your example. You can only identify errors with sufficient coverage.  
  
  ---
  
  