A survey of sequence alignment algorithms for next-generation sequencing.
Rapidly evolving sequencing technologies produce data on an unparalleled scale. A central challenge to the analysis of this data is sequence alignment, whereby sequence reads must be compared to a reference. A wide variety of alignment algorithms and software have been subsequently developed over the past two years. In this article, we will systematically review the current development of these algorithms and introduce their practical applications on different types of experimental data. We come to the conclusion that short-read alignment is no longer the bottleneck of data analyses. We also consider future development of alignment algorithms with respect to emerging long sequence reads and the prospect of cloud computing.
Li
Heng
H
Broad Institute, Cambridge, MA 02142, USA. hengli@broadinstitute.org
Homer
Nils
N
D000465:Algorithms; D001483:Base Sequence; D015894:Genome, Human; D006801:Humans; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
Genome Res. 2001 Oct;11(10):1725-9
11591649
BMC Bioinformatics. 2009 Jun 09;10:175
19508732
Genome Biol. 2009;10(3):R25
19261174
Bioinformatics. 2009 Jun 1;25(11):1363-9
19357099
PLoS Comput Biol. 2009 May;5(5):e1000386
19461883
Genome Res. 2008 Dec;18(12):2024-33
18818371
Bioinformatics. 2010 Mar 1;26(5):676-7
20071372
Bioinformatics. 2010 Apr 1;26(7):873-81
20147302
Bioinformatics. 2010 Apr 15;26(8):1029-35
20190250
Bioinformatics. 2010 Mar 15;26(6):722-9
20144947
Brief Bioinform. 2010 Jan;11(1):3-14
20053733
Genome Res. 2009 Jun;19(6):1117-23
19251739
PLoS Comput Biol. 2009 Sep;5(9):e1000502
19750212
J Mol Biol. 1990 Oct 5;215(3):403-10
2231712
Bioinformatics. 2009 Oct 1;25(19):2514-21
19675096
Bioinformatics. 2009 Jul 15;25(14):1754-60
19451168
Genome Biol. 2009;10(11):R134
19930550
Genome Res. 2009 Nov;19(11):2125-32
19679872
BMC Bioinformatics. 2009 Jul 27;10:232
19635165
Genome Biol. 2009;10(9):R98
19761611
Nat Methods. 2009 Sep;6(9):677-81
19668202
Genome Res. 2009 Sep;19(9):1646-54
19592482
Bioinformatics. 2009 Jan 1;25(1):6-13
18974170
Bioinformatics. 2010 Mar 1;26(5):589-95
20080505
Genome Biol. 2004;5(2):R12
14759262
Nat Rev Genet. 2010 Jan;11(1):31-46
19997069
BMC Bioinformatics. 2005 Feb 15;6:31
15713233
Bioinformatics. 2009 Aug 1;25(15):1966-7
19497933
BMC Bioinformatics. 2008 Feb 28;9:128
18307793
Bioinformatics. 2002 Mar;18(3):440-5
11934743
J Comput Biol. 1997 Fall;4(3):369-83
9278066
PLoS One. 2009 Nov 11;4(11):e7767
19907642
Nat Biotechnol. 2010 Jan;28(1):57-63
19997067
Bioinformatics. 2008 Mar 1;24(5):713-4
18227114
Bioinformatics. 2008 Oct 15;24(20):2395-6
18697769
Bioinformatics. 2010 Jan 1;26(1):38-45
19861355
Bioinformatics. 2010 Feb 1;26(3):401-2
19965881
Nat Methods. 2009 Nov;6(11 Suppl):S6-S12
19844229
Nature. 2008 Mar 13;452(7184):215-9
18278030
Genome Res. 2010 Feb;20(2):265-72
20019144
Bioinformatics. 2009 May 1;25(9):1105-11
19289445
Nat Methods. 2008 Jul;5(7):621-8
18516045
Genome Res. 2008 Nov;18(11):1851-8
18714091
Genome Res. 2002 Apr;12(4):656-64
11932250
Nat Methods. 2009 Nov;6(11 Suppl):S22-32
19844228
Bioinformatics. 2008 Mar 15;24(6):791-7
18227115
J Mol Biol. 1982 Dec 15;162(3):705-8
7166760
Nucleic Acids Res. 1997 Sep 1;25(17):3389-402
9254694
J Mol Biol. 1981 Mar 25;147(1):195-7
7265238
Bioinformatics. 2009 Sep 1;25(17):2283-5
19542151
Bioinformatics. 2007 Jan 15;23(2):156-61
17110365
Bioinformatics. 2008 Aug 15;24(16):i174-80
18689821
Bioinformatics. 2008 Nov 1;24(21):2431-7
18684737
Bioinformatics. 2009 Nov 1;25(21):2841-2
19736251
Bioinformatics. 2009 Aug 15;25(16):2078-9
19505943
Genome Res. 2002 Oct;12(10):1599-610
12368253