title: The Subread aligner: fast, accurate and scalable read mapping by seed-and-vote.
abstract: Read alignment is an ongoing challenge for the analysis of data from sequencing technologies. This article proposes an elegantly simple multi-seed strategy, called seed-and-vote, for mapping reads to a reference genome. The new strategy chooses the mapped genomic location for the read directly from the seeds. It uses a relatively large number of short seeds (called subreads) extracted from each read and allows all the seeds to vote on the optimal location. When the read length is <160 bp, overlapping subreads are used. More conventional alignment algorithms are then used to fill in detailed mismatch and indel information between the subreads that make up the winning voting block. The strategy is fast because the overall genomic location has already been chosen before the detailed alignment is done. It is sensitive because no individual subread is required to map exactly, nor are individual subreads constrained to map close by other subreads. It is accurate because the final location must be supported by several different subreads. The strategy extends easily to find exon junctions, by locating reads that contain sets of subreads mapping to different exons of the same gene. It scales up efficiently for longer reads.
authors.affiliation: Division of Bioinformatics, The Walter and Eliza Hall Institute of Medical Research, 1G Royal Parade, Parkville, Victoria 3052, Australia.
authors.forename: Yang
authors.initials: Y
authors.lastname: Liao
authors.forename: Gordon K
authors.initials: GK
authors.lastname: Smyth
authors.forename: Wei
authors.initials: W
authors.lastname: Shi
mesh_terms: D005091:Exons; D023281:Genomics; D059014:High-Throughput Nucleotide Sequencing; D054643:INDEL Mutation; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
references.citation: Nucleic Acids Res. 2012 May;40(10):4288-97
references.pmid: 22287627
references.citation: Brief Bioinform. 2010 Sep;11(5):473-83
references.pmid: 20460430
references.citation: Nucleic Acids Res. 2010 Dec;38(22):e204
references.pmid: 20929874
references.citation: PLoS One. 2009 Nov 11;4(11):e7767
references.pmid: 19907642
references.citation: Bioinformatics. 2012 Feb 15;28(4):593-4
references.pmid: 22199392
references.citation: J Mol Biol. 1970 Mar;48(3):443-53
references.pmid: 5420325
references.citation: Cell Rep. 2013 Feb 21;3(2):411-26
references.pmid: 23375371
references.citation: Genome Biol. 2010;11(10):R106
references.pmid: 20979621
references.citation: Bioinformatics. 2011 Apr 1;27(7):1011-2
references.pmid: 21278192
references.citation: Nat Methods. 2012 Dec;9(12):1185-8
references.pmid: 23103880
references.citation: J Neural Transm (Vienna). 2012 Mar;119(3):383-6
references.pmid: 21833492
references.citation: Bioinformatics. 2008 Nov 1;24(21):2431-7
references.pmid: 18684737
references.citation: Nat Genet. 2012 Sep;44(9):1060-5
references.pmid: 22885923
references.citation: Bioinformatics. 2009 Jul 15;25(14):1754-60
references.pmid: 19451168
references.citation: Nat Genet. 2007 May;39(5):605-13
references.pmid: 17450141
references.citation: J Comput Biol. 2006 Mar;13(2):296-308
references.pmid: 16597241
references.citation: Nat Methods. 2010 Aug;7(8):576-7
references.pmid: 20676076
references.citation: Genome Res. 2012 Dec;22(12):2489-96
references.pmid: 22879430
references.citation: Nat Methods. 2005 Oct;2(10):731-4
references.pmid: 16179916
references.citation: Genome Biol. 2009;10(3):R25
references.pmid: 19261174
references.citation: Nature. 2010 Oct 28;467(7319):1061-73
references.pmid: 20981092
references.citation: Nat Biotechnol. 2010 May;28(5):511-5
references.pmid: 20436464
references.citation: BMC Bioinformatics. 2011 Oct 05;12 Suppl 9:S15
references.pmid: 22151882
references.citation: BMC Bioinformatics. 2011 May 26;12:210
references.pmid: 21615913
references.citation: Bioinformatics. 2010 Mar 1;26(5):589-95
references.pmid: 20080505
references.citation: Nucleic Acids Res. 2008 Oct;36(17):e108
references.pmid: 18676452
references.citation: Biostatistics. 2003 Apr;4(2):249-64
references.pmid: 12925520
references.citation: Genome Res. 2011 Dec;21(12):2026-37
references.pmid: 21873453
references.citation: Nat Genet. 2011 May;43(5):491-8
references.pmid: 21478889
references.citation: Bioinformatics. 2007 Nov 1;23(21):2881-7
references.pmid: 17881408
references.citation: Bioinformatics. 2010 Jan 1;26(1):139-40
references.pmid: 19910308
references.citation: Bioinformatics. 2009 May 1;25(9):1105-11
references.pmid: 19289445
references.citation: Bioinformatics. 2010 Apr 1;26(7):873-81
references.pmid: 20147302
references.citation: Nat Methods. 2012 Mar 04;9(4):357-9
references.pmid: 22388286
references.citation: Genome Res. 2008 Nov;18(11):1851-8
references.pmid: 18714091
references.citation: BMC Bioinformatics. 2010 Aug 10;11:422
references.pmid: 20698981
references.citation: Nucleic Acids Res. 2011 Jun;39(11):4664-79
references.pmid: 21317192
references.citation: Bioinformatics. 2010 Oct 15;26(20):2534-40
references.pmid: 20739310
references.citation: Genome Biol. 2010;11(8):R83
references.pmid: 20701754
references.citation: Bioinformatics. 2011 Jan 15;27(2):189-95
references.pmid: 21088030
references.citation: J Mol Biol. 1981 Mar 25;147(1):195-7
references.pmid: 7265238
references.citation: Nucleic Acids Res. 2010 Oct;38(18):e178
references.pmid: 20802226
references.citation: BMC Res Notes. 2008 Jun 04;1:18
references.pmid: 18710543
references.citation: Bioinformatics. 2009 Aug 15;25(16):2078-9
references.pmid: 19505943
references.citation: Bioinformatics. 2003 Jan 22;19(2):185-93
references.pmid: 12538238
references.citation: Bioinformatics. 2012 Oct 15;28(20):2592-9
references.pmid: 22923295
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712
references.citation: Nat Biotechnol. 2006 Sep;24(9):1151-61
references.pmid: 16964229