 | This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages) (Learn how and when to remove this template message)
|
In bioinformatics, a DNA read error occurs when a sequence assembler changes one DNA base for a different base. The reads from the sequence assembler can then be used to create a de Bruijn graph, which can be used in various ways to find errors.
In a de Bruijn graph, there is a possibility of 4^k different nodes to make arrangements of a genome. The number of nodes used to create the graph can be reduced in number by considering only the k-mers found within the DNA strand of interest. Given sequence 1, it is possible to determine the nodes of size 7, or 7-mers, that will be in the graph. These 7-mers then create the graph shown in figure 1. [1]
The graph shown in figure 1 is a very simple version of what a graph could look like. [2] This graph is formed by taking the last 6 elements of the 7-mer and linking it to the node whose first 6 elements are the same. Figure 1 is the most simplistic a de Bruijn graph can be, since each node has exactly one path into it and one path out. Most of the time, graphs will have more than one edge directed to a node and/or more than one edge leaving a node. This happens due to the way nodes are connected. The nodes are connected by edges pointing to nodes if the last k-1 elements of the k-mer match the first k-1 elements of any node. This allows for a multiple-edged de Bruijn graph to form. These more complicated graphs happen due to either read errors or variations in DNA strands. Both causes make it difficult to determine the correct structure of the DNA, and what is causing the differences. Since most DNA strands will likely include read errors and variations, scientists hope to use an assembly process that can merge nodes of the graph when they are unambiguously connected after the graph has been cleaned of vertices and edges created by the errors. [3]
When a graph is formed from sequenced data, the read errors form tips and bubbles. A tip is where an error occurred during the sequencing process and has caused the graph to end prematurely and includes both correct and incorrect k-mers. A bubble is also formed when an error occurs during the sequence reading process; however, wherever the error happens, there is a path for the k-mer reads to reconnect with the main graph and continue as though nothing had ever happened. When there are tips and bubbles present in a de Bruijn graph formed from the data, they may be removed only if an error is what caused the tip or bubble to appear. When scientists are using a reference genome, they can quickly and easily tell where tips are located by comparing the graph of the reference genome and the graph of the sequence. If there is not a reference genome, tips are eliminated by tracing the branches backward until a point of ambiguity is found. Tips are then removed only if the branch containing the tip is shorter than a set threshold length. [3] The process of removing bubbles is slightly more complicated. The first thing that needs done is to identify the beginning of the bubble. From there, each path from the beginning of the bubble is followed until the point of reconnection. The point of reconnection can be different for each path. Since there can be paths of various lengths from the beginning node, the path which has a lower coverage is removed. [3]
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.
| ACAG (5X) | ACGC | AGAA | AGAC (9X) | AGAG (9X) | AGAT (8X) |
| AGGC (16X) | AGTC (7X) | ATCC (7X) | ATGA (8X) | CCGA (7X) | CGAC |
| CGAG (8X) | CGAT (6X) | CTAG (2X) | CTCT | CTTT (8X) | GACA (8X) |
| GACG | GAGA (12X) | GAGG (16X) | GATG (5X) | GATC (8X) | GATT |
| GCTC (2X) | GCTT (8X) | GGCT (11X) | GTCG (9X) | TAGA (16X) | TAGT (3X) |
| TCCG (7X) | TCGA (10X) | TCTA (2X) | TGAG (9X) | TTAG (12X) | TTTA (8X) |
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.
 The de Bruijn graph with linear stretches identified |  Simplified de Bruijn graph |
 The de Bruijn graph with tips and bubbles identified |  Final de Bruijn graph from DNA strand |
When comparing two strands of DNA, colored de Bruijn graphs are frequently used to identify errors. These errors, often polymorphisms, cause bubbles, similar to the ones mentioned above, to form. Currently there are four main algorithms used to generalize the data and locate bubbles. The four algorithms extend de Bruijn graphs by allowing the nodes and edges in the graph to be colored by the samples from which they were observed [5]
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]
In genetics, shotgun sequencing is a method used for sequencing random DNA strands. It is named by analogy with the rapidly expanding, quasi-random firing pattern of a shotgun.
A DNA sequencer is a scientific instrument used to automate the DNA sequencing process. Given a sample of DNA, a DNA sequencer is used to determine the order of the four bases: G (guanine), C (cytosine), A (adenine) and T (thymine). This is then reported as a text string, called a read. Some DNA sequencers can be also considered optical instruments as they analyze light signals originating from fluorochromes attached to nucleotides.
DNA sequencing is the process of determining the nucleic acid sequence – the order of nucleotides in DNA. It includes any method or technology that is used to determine the order of the four bases: adenine, guanine, cytosine, and thymine. The advent of rapid DNA sequencing methods has greatly accelerated biological and medical research and discovery.
Sanger sequencing is a method of DNA sequencing based on the selective incorporation of chain-terminating dideoxynucleotides by DNA polymerase during in vitro DNA replication. After first being developed by Frederick Sanger and colleagues in 1977, it became the most widely used sequencing method for approximately 40 years. It was first commercialized by Applied Biosystems in 1986. More recently, higher volume Sanger sequencing has been replaced by "Next-Gen" sequencing methods, especially for large-scale, automated genome analyses. However, the Sanger method remains in wide use, for smaller-scale projects, and for validation of Next-Gen results. It still has the advantage over short-read sequencing technologies in that it can produce DNA sequence reads of > 500 nucleotides.
In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. If we have the set of m symbols then the set of vertices is:
In bioinformatics, k-mers are subsequences of length contained within a biological sequence. Primarily used within the context of computational genomics and sequence analysis, in which k-mers are composed of nucleotides, k-mers are capitalized upon to assemble DNA sequences, improve heterologous gene expression, identify species in metagenomic samples, and create attenuated vaccines. Usually, the term k-mer refers to all of a sequence's subsequences of length , such that the sequence AGAT would have four monomers, three 2-mers, two 3-mers and one 4-mer (AGAT). More generally, a sequence of length will have k-mers and total possible k-mers, where is number of possible monomers.
2 Base Encoding, also called SOLiD, is a next-generation sequencing technology developed by Applied Biosystems and has been commercially available since 2008. These technologies generate hundreds of thousands of small sequence reads at one time. Well-known examples of such DNA sequencing methods include 454 pyrosequencing, the Solexa system and the SOLiD system. These methods have reduced the cost from $0.01/base in 2004 to nearly $0.0001/base in 2006 and increased the sequencing capacity from 1,000,000 bases/machine/day in 2004 to more than 100,000,000 bases/machine/day in 2006.
Velvet is an algorithm package that has been designed to deal with de novo genome assembly and short read sequencing alignments. This is achieved through the manipulation of de Bruijn graphs for genomic sequence assembly via the removal of errors and the simplification of repeated regions. Velvet has also been implemented in commercial packages, such as Sequencher, Geneious, MacVector and BioNumerics.
RNA-Seq is a particular technology-based sequencing technique which uses next-generation sequencing (NGS) to reveal the presence and quantity of RNA in a biological sample at a given moment, analyzing the continuously changing cellular transcriptome.
In bioinformatics, hybrid genome assembly refers to utilizing various sequencing technologies to achieve the task of assembling a genome from fragmented, sequenced DNA resulting from shotgun sequencing. Genome assembly presents one of the most challenging tasks in genome sequencing as most modern DNA sequencing technologies can only produce reads that are, on average, 25-300 base pairs in length. This is orders of magnitude smaller than the average size of a genome. This assembly is computationally difficult and has some inherent challenges, one of these challenges being that genomes often contain complex tandem repeats of sequences that can be thousands of base pairs in length. These repeats can be long enough that second generation sequencing reads are not long enough to bridge the repeat, and, as such, determining the location of each repeat in the genome can be difficult. Resolving these tandem repeats can be accomplished by utilizing long third generation sequencing reads, such as those obtained using the PacBio RS DNA sequencer. These sequences are, on average, 10,000-15,000 base pairs in length and are long enough to span most repeated regions. Using a hybrid approach to this process can increase the fidelity of assembling tandem repeats by being able to accurately place them along a linear scaffold and make the process more computationally efficient.
De novo transcriptome assembly is the de novo sequence assembly method of creating a transcriptome without the aid of a reference genome.
In bioinformatics, alignment-free sequence analysis approaches to molecular sequence and structure data provide alternatives over alignment-based approaches.
SPAdes is a genome assembly algorithm which was designed for single cell and multi-cells bacterial data sets. Therefore, it might not be suitable for large genomes projects.
SNV calling from NGS data is any of a range of methods for identifying the existence of single nucleotide variants (SNVs) from the results of next generation sequencing (NGS) experiments. These are computational techniques, and are in contrast to special experimental methods based on known population-wide single nucleotide polymorphisms. Due to the increasing abundance of NGS data, these techniques are becoming increasingly popular for performing SNP genotyping, with a wide variety of algorithms designed for specific experimental designs and applications. In addition to the usual application domain of SNP genotyping, these techniques have been successfully adapted to identify rare SNPs within a population, as well as detecting somatic SNVs within an individual using multiple tissue samples.
Duplex sequencing is a library preparation and analysis method for next-generation sequencing (NGS) platforms that employs random tagging of double stranded DNA to detect mutations with higher accuracy and lower error rate. This method uses degenerate molecular tags in addition to sequencing adapters to recognize reads originating from each strand of DNA. The generated sequencing reads then will be analyzed using two methods: single strand consensus sequences (SSCSs) and Duplex consensus sequences (DCSs) assembly. Duplex sequencing theoretically can detect mutations with frequencies as low as 5 x 10−8 that is more than 10,000 fold higher in accuracy compared to the conventional next-generation sequencing methods.
De novo sequence assemblers are a type of program that assembles short nucleotide sequences into longer ones without the use of a reference genome. These are most commonly used in bioinformatic studies to assemble genomes or transcriptomes. Two common types of de novo assemblers are greedy algorithm assemblers and De Bruijn graph assemblers.
Third-generation sequencing is a class of DNA sequencing methods currently under active development.
Bloom filters are space-efficient probabilistic data structures used to test whether an element is a part of a set. Bloom filters require much less space than other data structures for representing sets, however the downside of Bloom filters is that there is a false positive rate when querying the data structure. Since multiple elements may have the same hash values for a number of hash functions, then there is a probability that querying for a non-existent element may return a positive if another element with the same hash values has been added to the Bloom filter. Assuming that the hash function has equal probability of selecting any index of the Bloom filter, the false positive rate of querying a Bloom filter is a function of the number of bits, number of hash functions and number of elements of the Bloom filter. This allows the user to manage the risk of a getting a false positive by compromising on the space benefits of the Bloom filter.
