View source for De Novo Genome Assembly

{{DISPLAYTITLE:De Novo Genome Assembly (De Novo Genome Assembly)}}
== Description == 

De novo sequencing refers to sequencing a novel genome where there is no reference sequence available for alignment. Sequence reads are assembled as contigs, and the coverage quality of de novo sequence data depends on the size and continuity of the contigs (ie, the number of gaps in the data).

== Parameters == 

$n$: sum of lengths of reads

$f$: number of input sequences

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Overlap Layout Consensus (De Novo Genome Assembly De Novo Genome Assembly)|Overlap Layout Consensus]] || 1987 || $O(n^{2})$ || $O(n^{2})$? ||  || Deterministic ||  
|-
| [[Greedy SEQAID (De Novo Genome Assembly De Novo Genome Assembly)|Greedy SEQAID]] || 1984 || $O(n^{2})$? || $O(n^{2})$? ||  || Deterministic || [https://www-ncbi-nlm-nih-gov.ezproxy.canberra.edu.au/pmc/articles/PMC321006/ Time]
|-
| [[de Bruijn Graph (Idury, Waterman) (De Novo Genome Assembly De Novo Genome Assembly)|de Bruijn Graph (Idury, Waterman)]] || 1994 || $O(n^{2})$ || $O(n)$? || Exact || Deterministic || [https://www-ncbi-nlm-nih-gov.ezproxy.canberra.edu.au/pubmed/7497130 Time]
|-
| [[String Graph (Myers) (De Novo Genome Assembly De Novo Genome Assembly)|String Graph (Myers)]] || 1994 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://www-ncbi-nlm-nih-gov.ezproxy.canberra.edu.au/pubmed/7497129 Time]
|-
| [[String Graph with Ferragina–Manzini Index (Simpson, Durbin) (De Novo Genome Assembly De Novo Genome Assembly)|String Graph with Ferragina–Manzini Index (Simpson, Durbin)]] || 2010 || $O(n)$ || $O(n)$? || Exact || Deterministic || [https://www-ncbi-nlm-nih-gov.ezproxy.canberra.edu.au/pmc/articles/PMC2881401/pdf/btq217.pdf Time]
|-
| [[Hybrid Algorithm (De Novo Genome Assembly De Novo Genome Assembly)|Hybrid Algorithm]] || 1999 || $O(n^{2})$ ||  || Exact || Deterministic ||  
|-
|}

== Time Complexity Graph == 

[[File:De Novo Genome Assembly - Time.png|1000px]]

== Space Complexity Graph == 

[[File:De Novo Genome Assembly - Space.png|1000px]]

== Time-Space Tradeoff == 

[[File:De Novo Genome Assembly - Pareto Frontier.png|1000px]]