PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds.
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/
Chen
Yangho
Y
Program in Computational Biology and Bioinformatics, University of Southern California, 1050 Childs Way, Los Angeles, CA 90089-2910, USA.
Souaiaia
Tade
T
Chen
Ting
T
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D008969:Molecular Sequence Data; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
Bioinformatics. 2008 Dec 1;24(23):2776-7
18842598
Genome Biol. 2009;10(3):R25
19261174
Pharmacogenomics. 2004 Jun;5(4):433-8
15165179
Nat Methods. 2007 Aug;4(8):613-4
17664943
Bioinformatics. 2008 Nov 1;24(21):2431-7
18684737
IEEE/ACM Trans Comput Biol Bioinform. 2005 Jan-Mar;2(1):51-61
17044164
Bioinformatics. 2009 Jul 15;25(14):1754-60
19451168
BMC Bioinformatics. 2004 Oct 14;5:149
15485572
BMC Bioinformatics. 2008 Feb 28;9:128
18307793
Bioinformatics. 2002 Mar;18(3):440-5
11934743
Nat Biotechnol. 2008 Oct;26(10):1135-45
18846087
PLoS Comput Biol. 2009 May;5(5):e1000386
19461883
Bioinformatics. 2008 Mar 1;24(5):713-4
18227114
Bioinformatics. 2008 Oct 15;24(20):2395-6
18697769
Genome Res. 2008 Sep;18(9):1509-17
18550803
Bioinformatics. 2009 Jun 1;25(11):1424-5
19351619
J Comput Biol. 2005 Jul-Aug;12(6):847-61
16108721
J Comput Biol. 2006 Sep;13(7):1355-68
17037963
Genome Res. 2008 Nov;18(11):1851-8
18714091
Genome Res. 2002 Apr;12(4):656-64
11932250
Bioinformatics. 2009 Apr 1;25(7):969-70
19228804
Science. 1998 Jul 17;281(5375):363, 365
9705713
Nat Methods. 2008 Feb;5(2):179-81
18193056
Bioinformatics. 2009 Apr 1;25(7):967-8
19218350
J Mol Biol. 1990 Oct 5;215(3):403-10
2231712
J Bioinform Comput Biol. 2004 Sep;2(3):417-39
15359419