Home LiteratureArticle Details
PMID: 20460430 Published · ppublish English Journal Article Research Support, N.I.H., Extramural Review

A survey of sequence alignment algorithms for next-generation sequencing.

Briefings in bioinformatics ·Vol. 11 ·No. 5 ·2010-09-00 ·Pages 473-83

Li H, Homer N

Abstract

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.

MeSH Terms
Algorithms Base Sequence Genome, Human Humans Sequence Alignment/methods Sequence Analysis, DNA/methods Software
Authors & Affiliations
2 authors, click to expand affiliations / ORCID
Li Heng
Broad Institute, Cambridge, MA 02142, USA. [email protected]
Homer Nils
References (56)
56 references, click to expand
  1. SSAHA: a fast search method for large DNA databases.
    Genome Res. 2001 Oct;11(10):1725-9 PMID: 11591649
  2. Local alignment of two-base encoded DNA sequence.
    BMC Bioinformatics. 2009 Jun 09;10:175 PMID: 19508732
  3. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.
    Genome Biol. 2009;10(3):R25 PMID: 19261174
  4. CloudBurst: highly sensitive read mapping with MapReduce.
    Bioinformatics. 2009 Jun 1;25(11):1363-9 PMID: 19357099
  5. SHRiMP: accurate mapping of short color-space reads.
    PLoS Comput Biol. 2009 May;5(5):e1000386 PMID: 19461883
  6. Sequencing of natural strains of Arabidopsis thaliana with short reads.
    Genome Res. 2008 Dec;18(12):2024-33 PMID: 18818371
  7. BamView: viewing mapped read alignment data in the context of the reference sequence.
    Bioinformatics. 2010 Mar 1;26(5):676-7 PMID: 20071372
  8. Fast and SNP-tolerant detection of complex variants and splicing in short reads.
    Bioinformatics. 2010 Apr 1;26(7):873-81 PMID: 20147302
  9. High quality SNP calling using Illumina data at shallow coverage.
    Bioinformatics. 2010 Apr 15;26(8):1029-35 PMID: 20190250
  10. Microindel detection in short-read sequence data.
    Bioinformatics. 2010 Mar 15;26(6):722-9 PMID: 20144947
  11. Genome variation discovery with high-throughput sequencing data.
    Brief Bioinform. 2010 Jan;11(1):3-14 PMID: 20053733
  12. ABySS: a parallel assembler for short read sequence data.
    Genome Res. 2009 Jun;19(6):1117-23 PMID: 19251739
  13. Fast mapping of short sequences with mismatches, insertions and deletions using index structures.
    PLoS Comput Biol. 2009 Sep;5(9):e1000502 PMID: 19750212
  14. Basic local alignment search tool.
    J Mol Biol. 1990 Oct 5;215(3):403-10 PMID: 2231712
  15. PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds.
    Bioinformatics. 2009 Oct 1;25(19):2514-21 PMID: 19675096
  16. Fast and accurate short read alignment with Burrows-Wheeler transform.
    Bioinformatics. 2009 Jul 15;25(14):1754-60 PMID: 19451168
  17. Searching for SNPs with cloud computing.
    Genome Biol. 2009;10(11):R134 PMID: 19930550
  18. LookSeq: a browser-based viewer for deep sequencing data.
    Genome Res. 2009 Nov;19(11):2125-32 PMID: 19679872
  19. BSMAP: whole genome bisulfite sequence MAPping program.
    BMC Bioinformatics. 2009 Jul 27;10:232 PMID: 19635165
  20. Simultaneous alignment of short reads against multiple genomes.
    Genome Biol. 2009;10(9):R98 PMID: 19761611
  21. BreakDancer: an algorithm for high-resolution mapping of genomic structural variation.
    Nat Methods. 2009 Sep;6(9):677-81 PMID: 19668202
  22. RazerS--fast read mapping with sensitivity control.
    Genome Res. 2009 Sep;19(9):1646-54 PMID: 19592482
  23. Slider--maximum use of probability information for alignment of short sequence reads and SNP detection.
    Bioinformatics. 2009 Jan 1;25(1):6-13 PMID: 18974170
  24. Fast and accurate long-read alignment with Burrows-Wheeler transform.
    Bioinformatics. 2010 Mar 1;26(5):589-95 PMID: 20080505
  25. Versatile and open software for comparing large genomes.
    Genome Biol. 2004;5(2):R12 PMID: 14759262
  26. Sequencing technologies - the next generation.
    Nat Rev Genet. 2010 Jan;11(1):31-46 PMID: 19997069
  27. Automated generation of heuristics for biological sequence comparison.
    BMC Bioinformatics. 2005 Feb 15;6:31 PMID: 15713233
  28. SOAP2: an improved ultrafast tool for short read alignment.
    Bioinformatics. 2009 Aug 1;25(15):1966-7 PMID: 19497933
  29. Using quality scores and longer reads improves accuracy of Solexa read mapping.
    BMC Bioinformatics. 2008 Feb 28;9:128 PMID: 18307793
  30. PatternHunter: faster and more sensitive homology search.
    Bioinformatics. 2002 Mar;18(3):440-5 PMID: 11934743
  31. ReAligner: a program for refining DNA sequence multi-alignments.
    J Comput Biol. 1997 Fall;4(3):369-83 PMID: 9278066
  32. BFAST: an alignment tool for large scale genome resequencing.
    PLoS One. 2009 Nov 11;4(11):e7767 PMID: 19907642
  33. Building the sequence map of the human pan-genome.
    Nat Biotechnol. 2010 Jan;28(1):57-63 PMID: 19997067
  34. SOAP: short oligonucleotide alignment program.
    Bioinformatics. 2008 Mar 1;24(5):713-4 PMID: 18227114
  35. SeqMap: mapping massive amount of oligonucleotides to the genome.
    Bioinformatics. 2008 Oct 15;24(20):2395-6 PMID: 18697769
  36. The GNUMAP algorithm: unbiased probabilistic mapping of oligonucleotides from next-generation sequencing.
    Bioinformatics. 2010 Jan 1;26(1):38-45 PMID: 19861355
  37. Tablet--next generation sequence assembly visualization.
    Bioinformatics. 2010 Feb 1;26(3):401-2 PMID: 19965881
  38. Sense from sequence reads: methods for alignment and assembly.
    Nat Methods. 2009 Nov;6(11 Suppl):S6-S12 PMID: 19844229
  39. Shotgun bisulphite sequencing of the Arabidopsis genome reveals DNA methylation patterning.
    Nature. 2008 Mar 13;452(7184):215-9 PMID: 18278030
  40. De novo assembly of human genomes with massively parallel short read sequencing.
    Genome Res. 2010 Feb;20(2):265-72 PMID: 20019144
  41. TopHat: discovering splice junctions with RNA-Seq.
    Bioinformatics. 2009 May 1;25(9):1105-11 PMID: 19289445
  42. Mapping and quantifying mammalian transcriptomes by RNA-Seq.
    Nat Methods. 2008 Jul;5(7):621-8 PMID: 18516045
  43. Mapping short DNA sequencing reads and calling variants using mapping quality scores.
    Genome Res. 2008 Nov;18(11):1851-8 PMID: 18714091
  44. BLAT--the BLAST-like alignment tool.
    Genome Res. 2002 Apr;12(4):656-64 PMID: 11932250
  45. Computation for ChIP-seq and RNA-seq studies.
    Nat Methods. 2009 Nov;6(11 Suppl):S22-32 PMID: 19844228
  46. Compressed indexing and local alignment of DNA.
    Bioinformatics. 2008 Mar 15;24(6):791-7 PMID: 18227115
  47. An improved algorithm for matching biological sequences.
    J Mol Biol. 1982 Dec 15;162(3):705-8 PMID: 7166760
  48. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs.
    Nucleic Acids Res. 1997 Sep 1;25(17):3389-402 PMID: 9254694
  49. Identification of common molecular subsequences.
    J Mol Biol. 1981 Mar 25;147(1):195-7 PMID: 7265238
  50. VarScan: variant detection in massively parallel sequencing of individual and pooled samples.
    Bioinformatics. 2009 Sep 1;25(17):2283-5 PMID: 19542151
  51. Striped Smith-Waterman speeds database searches six times over other SIMD implementations.
    Bioinformatics. 2007 Jan 15;23(2):156-61 PMID: 17110365
  52. Optimal spliced alignments of short sequence reads.
    Bioinformatics. 2008 Aug 15;24(16):i174-80 PMID: 18689821
  53. ZOOM! Zillions of oligos mapped.
    Bioinformatics. 2008 Nov 1;24(21):2431-7 PMID: 18684737
  54. Updates to the RMAP short-read mapping software.
    Bioinformatics. 2009 Nov 1;25(21):2841-2 PMID: 19736251
  55. The Sequence Alignment/Map format and SAMtools.
    Bioinformatics. 2009 Aug 15;25(16):2078-9 PMID: 19505943
  56. The generic genome browser: a building block for a model organism system database.
    Genome Res. 2002 Oct;12(10):1599-610 PMID: 12368253
Article Info
Journal
Briefings in bioinformatics
Abbr.
Brief Bioinform
ISSN
1477-4054
DOI
10.1093/bib/bbq015
Email
[email protected]
Published
2010-09-00
Epub
2010-00-11
Pages
473-83
Language
English
Region
England
NLM ID
100912837
PMCID
PMC2943993
Subset
IM
Grants
NHGRI NIH HHS · 1U01HG005208-01 · United States
NHGRI NIH HHS · 1U01HG005210-01 · United States
External Links
PubMed source DOI: 10.1093/bib/bbq015 PMC Full Text View journal details
Analysis Services
Analysis Services

Contact

No. 2 Wenbo Road, Zhangqiu District, Jinan, Shandong

Qilu Normal University · Genelibs Bioinformatics Lab

750 Shunhua Rd, Jinan

2F, Bldg F, University Science Park

Tel: 0531-88819269

WeChat Official Account

Follow our WeChat subscription account for real-time updates and the latest in medical and biological research.


Business Email

E-mail: [email protected]

Copyright © 2026.Genelibs Jinan Honghui Biotechnology Co., Ltd. 鲁ICP备20007159号-2