View source for Software:Velvet assembler

{{Short description|Algorithm package}}
{{Infobox software
| developer = Daniel Zerbino,<ref>{{Cite book | pmid = 20836074 | year = 2010 | last1 = Zerbino | first1 = D. R. | title = Using the Velvet de novo assembler for short-read sequencing technologies |editor=Andreas D. Baxevanis | pages = Unit 11.5 | doi = 10.1002/0471250953.bi1105s31 | chapter = Using the Velvetde novo ''Assembler'' for Short-Read Sequencing Technologies | journal = Current Protocols in Bioinformatics | volume = 31 | isbn = 978-0471250951 | pmc = 2952100}}</ref> [[Biography:Ewan Birney|Ewan Birney]]
| released = 2008
| latest release version = 1.2.10
| latest release date = 
| latest preview version = 
| latest preview date = 
| programming language = 
| operating system = [[Unix-like]]
| platform = 
| size = 
| language = C
| genre = Bioinformatics
| license = [[Software:GNU General Public License|GPL]]
| website = {{URL|www.github.com/dzerbino/velvet/}}
}}
'''Velvet''' is an algorithm package that has been designed to deal with ''de novo'' genome assembly and short read [[Sequence alignment|sequencing alignments]]. This is achieved through the manipulation of [[De Bruijn graph|de Bruijn graph]]s for genomic sequence assembly via the removal of errors and the simplification of repeated regions.<ref name=poster>Zerbino, D. R.; Birney, E. (2008). [http://www.ebi.ac.uk/~zerbino/velvet/velvet_poster.pdf "Velvet: de novo assembly using very short reads"]. Retrieved 18 October 2013.</ref> Velvet has also been implemented in commercial packages, such as Sequencher, [[Software:Biomatters|Geneious]], [[Software:MacVector|MacVector]] and [[Software:BioNumerics|BioNumerics]].

==Introduction==
The development of next-generation sequencers (NGS) allowed for increased cost effectiveness on very short read sequencing. The manipulation of de Bruijn graphs as a method for alignment became more realistic but further developments were needed to address issues with errors and repeats.<ref name=miller>{{Cite journal
 | pmid = 20211242
| year = 2010
| last1 = Miller
| first1 = J. R.
| title = Assembly algorithms for next-generation sequencing data
| journal = Genomics
| volume = 95
| issue = 6
| pages = 315–27
| last2 = Koren
| first2 = S
| last3 = Sutton
| first3 = G
| doi = 10.1016/j.ygeno.2010.03.001
| pmc = 2874646
}}</ref> This led to the development of Velvet by Daniel Zerbino and [[Biography:Ewan Birney|Ewan Birney]] at the [[Organization:European Bioinformatics Institute|European Bioinformatics Institute]] in the United Kingdom.<ref name=zerbino>{{Cite journal 
| last1 = Zerbino | first1 = D. R. 
| last2 = Birney | first2 = E. 
| doi = 10.1101/gr.074492.107 
| title = Velvet: Algorithms for de novo short read assembly using de Bruijn graphs 
| journal = Genome Research 
| volume = 18 
| issue = 5 
| pages = 821–829 
| year = 2008 
| pmid = 18349386 
| pmc =2336801 
}}</ref>

Velvet works by efficiently manipulating de Bruijn graphs through simplification and compression, without the loss of graph information, by converging non-intersecting paths into single nodes. It eliminates errors and resolves repeats by first using an error correction algorithm that merges sequences together. Repeats are then removed from the sequence via the repeat solver that separates paths which share local overlaps.

The combination of short reads and read pairs allows Velvet to resolve small repeats and produce [[Biology:Contig|contig]]s of reasonable length. This application of Velvet can produce contigs with a N50 length of 50 kb on paired-end prokaryotic data and a 3 kb length for regions of [[Biology:Mammal|mammal]]ian data.

==Algorithm==
As already mentioned Velvet uses the de Bruijn graph to assemble short reads. More specifically Velvet represents each different [[K-mer|k-mer]] obtained from the reads by a unique node on the graph. Two nodes are connected if its k-mers have a k-1 overlap.  In other words, an arc from node A to node B exists if the last k-1 characters of the k-mer, represented by A, are the first k-1 characters of the k-mer represented by B.   The following figure shows an example of a de Bruijn graph generated with Velvet:

[[File:Example 1seq.pdf|thumb|center|middle|upright=3.0| Figure 1: Example of read hashing and respective de Bruijn graph]]

The same process is simultaneously done with the [[Biology:Complementarity (molecular biology)|reverse complement]] of all the k-mers to take into account the overlaps between the reads of opposite strands.
A number of optimizations can be done over the graph which includes simplification and error removal.

===Simplification===
An easy way to save memory costs is to merge nodes that do not affect the path generated in the graph, i.e., whenever a node A has only one outgoing arc that points to node B, with only one ingoing arc, the nodes can be merged. It is possible to represent both nodes as one, merging them and all their information together. The next figure illustrates this process in the simplification of the initial example.

[[File:Example 2simp.pdf|thumb|center|middle|upright=3.0| Figure 2: Simplified de Bruijn graph]]

===Error removal===
Errors in the graph can be caused by the sequencing process or it could simply be that the biological sample contains some errors (for example [[Biology:Polymorphism|polymorphism]]s).  
Velvet recognizes three kinds of errors: tips; bubbles; and erroneous connections.

====Tips====
A node is considered a tip and should be erased if it is disconnected on one of its ends, the length of the information stored in the node is shorter than 2k, and the arc leading to this node has a low multiplicity (number of times the arc was found during the construction of the graph) and as a result cannot be compared to other alternative paths. Once these errors are removed, the graph once again undergoes simplification.

[[File:Example 3.pdf|thumb|center|middle|upright=3.0| Figure 3: Example of tips]]

====Bubbles====
Bubbles are generated when two distinct paths start and end at the same nodes. Normally bubbles are caused by errors or biological variants. These errors are removed using the Tour Bus algorithm, which is similar to a [[Dijkstra's algorithm]], a [[Breadth-first search|breadth-first search]] that detects the best path to follow and determines which ones should be erased.  A simple example is shown in figure 4.

[[File:Example 4.pdf|thumb|center|middle|upright=3.0| Figure 4: Example of bubble erase]]

This process is also shown in figure 5 following on from the examples shown in figures 1 and 2.

[[File:Example 5.pdf|thumb|center|middle|upright=3.0| Figure 5: Example of bubble detection]]

====Erroneous connections====
These are connections that do not generate correct paths or do not create any recognizable structures within the graph. Velvet erases these errors after completion of the Tour Bus algorithm, applying a simple coverage cut-off that must be defined by the user.

==Velvet commands==
Velvet provides the following functions:
; velveth : This command helps to construct the data set (hashes the reads) for velvetg and includes information about the meaning of each sequence files. 
; velvetg : This command builds the de Bruijn graph from the k-mers obtained by velveth and runs simplification and error correction over the graph. It then extracts the contigs.

After running velvetg a number of files are generated. Most importantly, a file of contigs contains the sequences of the contigs longer than 2k, where k is the word-length used in velveth.

For more detail and examples refer to the [http://www.ebi.ac.uk/~zerbino/velvet/Manual.pdf Velvet Manual] <ref name=manual>[http://www.ebi.ac.uk/~zerbino/velvet/Manual.pdf "Velvet Manual"] Retrieved 18 October 2013</ref>

==Motivation==
Current DNA sequencing technologies, including NGS, are limited on the basis that [[Biology:Genome|genome]]s are much larger than any read length. Typically, NGS operate with small reads, less than 400 bp, and have a much lower cost per read than previous [[Biology:DNA sequencing|first generation machines]]. They are also simpler to operate with higher parallel operation and higher yield.<ref name=miller/>

However, short reads contain less information than larger reads thus requiring a higher assembly read coverage to allow for detectable overlaps. This in turn increases the complexity of the sequencing and significantly increases computational requirements. A larger number of reads also increases the size of the overlap graph, making it more difficult and lengthy to compute. The connections between the reads become more indistinct due to the decrease in overlapping sections leading to a greater possibility of errors.

To overcome these issues, dynamic sequencing programs that are efficient, highly cost effective and able to resolve errors and repeats were developed. Velvet algorithms was designed for this and are able to perform short read de novo sequencing alignment in relatively short computational time and with lower memory usage compared to other assemblers.<ref name=zang>{{Cite journal | doi = 10.1371/journal.pone.0017915| pmid = 21423806| title = A Practical Comparison of De Novo Genome Assembly Software Tools for Next-Generation Sequencing Technologies| journal = PLOS ONE| volume = 6| issue = 3| pages = e17915| year = 2011| last1 = Zhang | first1 = W. | last2 = Chen | first2 = J. | last3 = Yang | first3 = Y. | last4 = Tang | first4 = Y. | last5 = Shang | first5 = J. | last6 = Shen | first6 = B. | pmc=3056720| bibcode = 2011PLoSO...617915Z| doi-access = free}}</ref>

==Graphical interface==
One of the main drawbacks in the use of Velvet is the use of the command-line interface and the difficulties users, especially beginners, face in the implementation of their data. A graphical user interface for the Velvet assembler was developed in 2012 and designed to overcome this problem and simplify the running of Velvet.<ref name=vague>{{Cite journal
 | pmid = 23162059
| year = 2013
| last1 = Powell
| first1 = D. R.
| title = VAGUE: A graphical user interface for the Velvet assembler
| journal = Bioinformatics
| volume = 29
| issue = 2
| pages = 264–5
| last2 = Seemann
| first2 = T
| doi = 10.1093/bioinformatics/bts664
| doi-access = free
}}</ref>

== See also ==
* [[Biology:De novo sequence assemblers|De novo sequence assemblers]]
* [[Software:SPAdes|SPAdes]]

==References==
{{reflist}}

[[Category:Bioinformatics algorithms]]
[[Category:Bioinformatics software]]
[[Category:DNA sequencing]]
[[Category:Metagenomics software]]

{{Sourceattribution|Velvet assembler}}