title: PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds.
abstract: BACKGROUND
  The explosion of next-generation sequencing data has spawned the design of new algorithms and software tools to provide efficient mapping for different read lengths and sequencing technologies. In particular, ABI's sequencer (SOLiD system) poses a big computational challenge with its capacity to produce very large amounts of data, and its unique strategy of encoding sequence data into color signals.
  
  
  RESULTS
  We present the mapping software, named PerM (Periodic Seed Mapping) that uses periodic spaced seeds to significantly improve mapping efficiency for large reference genomes when compared with state-of-the-art programs. The data structure in PerM requires only 4.5 bytes per base to index the human genome, allowing entire genomes to be loaded to memory, while multiple processors simultaneously map reads to the reference. Weight maximized periodic seeds offer full sensitivity for up to three mismatches and high sensitivity for four and five mismatches while minimizing the number random hits per query, significantly speeding up the running time. Such sensitivity makes PerM a valuable mapping tool for SOLiD and Solexa reads.
  
  
  BACKGROUND
  http://code.google.com/p/perm/
authors.affiliation: Program in Computational Biology and Bioinformatics, University of Southern California, 1050 Childs Way, Los Angeles, CA 90089-2910, USA.
authors.forename: Yangho
authors.initials: Y
authors.lastname: Chen
authors.forename: Tade
authors.initials: T
authors.lastname: Souaiaia
authors.forename: Ting
authors.initials: T
authors.lastname: Chen
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D008969:Molecular Sequence Data; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
references.citation: Bioinformatics. 2008 Dec 1;24(23):2776-7
references.pmid: 18842598
references.citation: Genome Biol. 2009;10(3):R25
references.pmid: 19261174
references.citation: Pharmacogenomics. 2004 Jun;5(4):433-8
references.pmid: 15165179
references.citation: Nat Methods. 2007 Aug;4(8):613-4
references.pmid: 17664943
references.citation: Bioinformatics. 2008 Nov 1;24(21):2431-7
references.pmid: 18684737
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2005 Jan-Mar;2(1):51-61
references.pmid: 17044164
references.citation: Bioinformatics. 2009 Jul 15;25(14):1754-60
references.pmid: 19451168
references.citation: BMC Bioinformatics. 2004 Oct 14;5:149
references.pmid: 15485572
references.citation: BMC Bioinformatics. 2008 Feb 28;9:128
references.pmid: 18307793
references.citation: Bioinformatics. 2002 Mar;18(3):440-5
references.pmid: 11934743
references.citation: Nat Biotechnol. 2008 Oct;26(10):1135-45
references.pmid: 18846087
references.citation: PLoS Comput Biol. 2009 May;5(5):e1000386
references.pmid: 19461883
references.citation: Bioinformatics. 2008 Mar 1;24(5):713-4
references.pmid: 18227114
references.citation: Bioinformatics. 2008 Oct 15;24(20):2395-6
references.pmid: 18697769
references.citation: Genome Res. 2008 Sep;18(9):1509-17
references.pmid: 18550803
references.citation: Bioinformatics. 2009 Jun 1;25(11):1424-5
references.pmid: 19351619
references.citation: J Comput Biol. 2005 Jul-Aug;12(6):847-61
references.pmid: 16108721
references.citation: J Comput Biol. 2006 Sep;13(7):1355-68
references.pmid: 17037963
references.citation: Genome Res. 2008 Nov;18(11):1851-8
references.pmid: 18714091
references.citation: Genome Res. 2002 Apr;12(4):656-64
references.pmid: 11932250
references.citation: Bioinformatics. 2009 Apr 1;25(7):969-70
references.pmid: 19228804
references.citation: Science. 1998 Jul 17;281(5375):363, 365
references.pmid: 9705713
references.citation: Nat Methods. 2008 Feb;5(2):179-81
references.pmid: 18193056
references.citation: Bioinformatics. 2009 Apr 1;25(7):967-8
references.pmid: 19218350
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712
references.citation: J Bioinform Comput Biol. 2004 Sep;2(3):417-39
references.pmid: 15359419