DNA read errors

sequence 2

Given a sequence of any length, the first step that needs done is to enter the sequence into a sequencing program, have it sequenced, and a return base pair (bp) reads of a certain length. Since there is not a sequencing program that is completely accurate, there will always be some reads which contain errors. The most common sequencing method is the shotgun method, which is the method most probably used on sequence 2. Once a method is decided on, you have to specify the length of the bp reads you would like it to return. In the case of sequence 2, it returned 7-bp reads with all errors made during the process noted in red.[4]

Once the reads are obtained, they are hashed into k-mers. The k-mers then are recorded in a table with how many times each k-mer appeared in the reads. For this example, each read was hashed into 4-mers and if there was an error it was recorded in red. All of the 4-mers were then recorded, with their frequency in the following table.

Each individual cell of the table will then form a node, allowing a de Bruijn graph to be formed from the given k-mers. In figure 2, linear stretches are identified and then another graph, figure 3, is formed where the linear stretches have become a single node, of a different k-mer size, allowing for a more concise graph. In this simplified graph, it is easy to identify various tips and bubbles, as shown in figure 4. These bubbles and tips can then be removed, since we can identify that they were formed from errors in the bp reads, giving us a graph structure that should accurately and completely reflect the original sequence.[4] If you follow the de Bruijn graph shown in figure 5, you will see that the sequence formed does indeed match the DNA sequence given in sequence 2.

figure 2 The de Bruijn graph with linear stretches identified	figure 3 Simplified de Bruijn graph
figure 4 The de Bruijn graph with tips and bubbles identified	figure 5 Final de Bruijn graph from DNA strand

The simplest use of a colored de Bruijn graph is known as the bubble calling algorithm. This algorithm looks, and locates, bubbles on the genome that differ from the original. These bubbles must be “clean”, or simply a divergence from the reference genome, but cannot be caused by deletions of DNA bases. This algorithm can have high false positive rates since there is a difficulty of separating repeat- and variant-induced bubbles; however, there is often a reference genome to help improve reliability. The reference genome also helps in the detection of variants and is essential to detect variant sites.[5] Recently, scientists have discovered a way to use the bubble calling algorithm with copy number variation detection to allow for an opportunity of unbiased detection of these variations in the future[6][7]

When looking at complex variants, there is a very low chance that they will make a clean contig. Since this is the case most often, the path divergence algorithm is useful, especially when considering where deletions occur and the variant is so complex it is constrained to the reference allele. When there is a bubble formed, the path divergence algorithm is used the most frequently and allows detected bubbles to get deleted in a very systematic procedure. The algorithm first locates each point of divergence. Then from each point of divergence, the strands that form the bubble are traced to find where the two paths join after n nodes. If the two paths join, then the path with a lower coverage is removed and stored in a file.[3][8]

Using multiple samples substantially improves the power and false discovery rate of detecting variants. In the simplest cases, the samples are combined into a group of a single color and the data is analysed as described previously. However, by maintaining separate colors for each sample set, additional information on how the bubbles were formed, whether by error or by repeats, presents itself.[5] In 1997, the Department of Technology at Genzyme Genetics in Framingham, Massachusetts developed a new approach that provided a breakthrough in dealing with bubbles using the multiplex allele-specific diagnostic assay (MASDA). This program combines forward dot-blot, complex simultaneous probe hybridization and direct mutation detection to help solve the dual problem of multiple sample analysis.[9]

The colored de Bruijn graphs can be used to genotype any DNA sample at a known loci, even when the coverage is less than sufficient for variant assembly.[5] The first step to this process is to construct a graph of the reference allele, known variants and data from the sample. The algorithm then calculates the likelihood of each genotype and accounts for the structure of the graph, both of the local and genome-wide sequence. This then generalizes to multiple allelic types and helps genotype complex and compound variants.[5] This algorithm is used frequently, as there are no bubbles formed to deal with. This also directly helps find the more complicated issues in genes more direct than any of the three algorithms previously mentioned.[10]