{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:26:12Z","timestamp":1773275172735,"version":"3.50.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"19","license":[{"start":{"date-parts":[[2016,10,1]],"date-time":"2016-10-01T00:00:00Z","timestamp":1475280000000},"content-version":"vor","delay-in-days":2607,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: 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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability: \u00a0http:\/\/code.google.com\/p\/perm\/<\/jats:p>\n               <jats:p>Contact: \u00a0tingchen@usc.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp486","type":"journal-article","created":{"date-parts":[[2009,8,13]],"date-time":"2009-08-13T00:59:00Z","timestamp":1250125140000},"page":"2514-2521","source":"Crossref","is-referenced-by-count":80,"title":["PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds"],"prefix":"10.1093","volume":"25","author":[{"given":"Yangho","family":"Chen","sequence":"first","affiliation":[{"name":"Program in Computational Biology and Bioinformatics, University of Southern California, 1050 Childs Way, Los Angeles, CA 90089-2910, USA"}]},{"given":"Tade","family":"Souaiaia","sequence":"additional","affiliation":[{"name":"Program in Computational Biology and Bioinformatics, University of Southern California, 1050 Childs Way, Los Angeles, CA 90089-2910, USA"}]},{"given":"Ting","family":"Chen","sequence":"additional","affiliation":[{"name":"Program in Computational Biology and Bioinformatics, University of Southern California, 1050 Childs Way, Los Angeles, CA 90089-2910, USA"}]}],"member":"286","published-online":{"date-parts":[[2009,8,12]]},"reference":[{"key":"2023013112125199800_B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023013112125199800_B2","volume-title":"Principles of di-base sequencing and the advantage of color space analysis in the solid system.","author":"Applied Biosystems","year":"2008"},{"key":"2023013112125199800_B3","volume-title":"Principles of di-base sequencing and the advantage of color space analysis in the solid system.","author":"Applied Biosystems","year":"2008"},{"key":"2023013112125199800_B4","volume-title":"SOLiDTM system application documentation: Ab resequencing analysis pipeline (corona lite).","author":"Applied Biosystems","year":"2008"},{"key":"2023013112125199800_B5","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1517\/14622416.5.4.433","article-title":"Solexa ltd","volume":"5","author":"Bennett","year":"2004","journal-title":"Pharmacogenomics"},{"key":"2023013112125199800_B6","first-page":"67","article-title":"Designing seeds for similarity search in genomic DNA","volume-title":"Journal of Computer and System Sciences.","author":"Buhler","year":"2003"},{"key":"2023013112125199800_B7","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-48194-X_6","article-title":"Better filtering with gapped q-grams","volume-title":"Proceedings of the 12th Symposium on Combinatorial Pattern Matching (CPM'01).","author":"Burkhardt","year":"2001"},{"key":"2023013112125199800_B8","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1093\/bioinformatics\/btp087","article-title":"Pass: a program to align short sequences","volume":"25","author":"Campagna","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B9","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1093\/bioinformatics\/btp092","article-title":"MOM: maximum oligonucleotide mapping","volume":"25","author":"Eaves","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B10","doi-asserted-by":"crossref","first-page":"2395","DOI":"10.1093\/bioinformatics\/btn429","article-title":"SeqMap: mapping massive amount of oligonucleotides to the genome","volume":"24","author":"Jiang","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B11","first-page":"656","article-title":"BLAT\u2013the BLAST-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023013112125199800_B12","doi-asserted-by":"crossref","first-page":"1424","DOI":"10.1093\/bioinformatics\/btp178","article-title":"ProbeMatch: rapid alignment of oligonucleotides to genome allowing both gaps and mismatches","volume":"25","author":"Kim","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B13","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1109\/TCBB.2005.12","article-title":"Multiseed lossless filtration","volume":"2","author":"Kucherov","year":"2005","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023013112125199800_B14","doi-asserted-by":"crossref","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume-title":"Genome Biol.","author":"Langmead","year":"2009"},{"key":"2023013112125199800_B15","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B16","doi-asserted-by":"crossref","first-page":"2431","DOI":"10.1093\/bioinformatics\/btn416","article-title":"Zoom! zillions of oligos mapped","volume":"24","author":"Lin","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B17","doi-asserted-by":"crossref","first-page":"1851","DOI":"10.1101\/gr.078212.108","article-title":"Mapping short DNA sequencing reads and calling variants using mapping quality scores","volume":"18","author":"Li","year":"2008","journal-title":"Genome Res."},{"key":"2023013112125199800_B18","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1142\/S0219720004000661","article-title":"PatternHunter II: highly sensitive and fast homology search","volume":"2","author":"Li","year":"2004","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023013112125199800_B19","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1093\/bioinformatics\/btn025","article-title":"SOAP: short oligonucleotide alignment program","volume":"24","author":"Li","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B20","article-title":"Seed optimization is no easier than optimal Golomb ruler design","author":"Ma","year":"2008","journal-title":"Asia Pacific Bioinformatics Conference (APBC)."},{"key":"2023013112125199800_B21","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B22","volume-title":"SXOligoSearch.","author":"Malaysian Genomics Resource Center","year":"2009"},{"key":"2023013112125199800_B23","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1038\/nmeth0807-613","article-title":"ChIP-seq: welcome to the new frontier","volume":"4","author":"Mardis","year":"2007","journal-title":"Nat. Methods"},{"key":"2023013112125199800_B24","doi-asserted-by":"crossref","first-page":"1509","DOI":"10.1101\/gr.079558.108","article-title":"RNA-seq: an assessment of technical reproducibility and comparison with gene expression arrays","volume":"18","author":"Marioni","year":"2008","journal-title":"Genome Res."},{"key":"2023013112125199800_B25","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/316542.316550","article-title":"A fast bit-vector algorithm for approximate string matching based on dynamic programming","volume":"46","author":"Myers","year":"1999","journal-title":"J. ACM"},{"key":"2023013112125199800_B26","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1016\/j.jcss.2007.10.001","article-title":"Hardness of optimal spaced seed design","volume":"74","author":"Nicolas","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"2023013112125199800_B27","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1186\/1471-2105-5-149","article-title":"Improved hit criteria for DNA local alignment","volume":"5","author":"No\u00e9","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023013112125199800_B28","doi-asserted-by":"crossref","first-page":"2776","DOI":"10.1093\/bioinformatics\/btn512","article-title":"Efficient mapping of applied biosystems solid sequence data to a reference genome for functional genomic applications","volume":"24","author":"Ondov","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112125199800_B29","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1038\/nmeth.1172","article-title":"Pyrobayes: an improved base caller for SNP discovery in pyrosequences","volume":"5","author":"Quinlan","year":"2008","journal-title":"Nat. Methods"},{"key":"2023013112125199800_B30","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1126\/science.281.5375.363","article-title":"A sequencing method based on real-time pyrophosphate","volume":"281","author":"Ronaghi","year":"1998","journal-title":"Science"},{"key":"2023013112125199800_B31","doi-asserted-by":"crossref","first-page":"e1000386","DOI":"10.1371\/journal.pcbi.1000386","article-title":"SHRiMP: accurate mapping of short color-space reads","volume":"5","author":"Rumble","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023013112125199800_B32","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1038\/nbt1486","article-title":"Next-generation DNA sequencing","volume":"26","author":"Shendure","year":"2008","journal-title":"Nat. Biotechnol."},{"key":"2023013112125199800_B33","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1186\/1471-2105-9-128","article-title":"Using quality scores and longer reads improves accuracy of Solexa read mapping","volume":"9","author":"Smith","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023013112125199800_B34","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1089\/cmb.2005.12.847","article-title":"Designing multiple simultaneous seeds for DNA similarity search","volume":"12","author":"Sun","year":"2005","journal-title":"J. Comput. Biol."},{"key":"2023013112125199800_B35","volume-title":"Mosaik.","author":"The MarthLab","year":"2009"},{"key":"2023013112125199800_B36","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1089\/cmb.2006.13.1355","article-title":"Optimizing multiple spaced seeds for homology search","volume":"13","author":"Xu","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023013112125199800_B37","first-page":"411","article-title":"Efficient methods for generating optimal single and multiple spaced seeds","volume-title":"BIBE '04: Proceedings of the 4th IEEE Symposium on Bioinformatics and Bioengineering.","author":"Yang","year":"2004"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/19\/2514\/48995397\/bioinformatics_25_19_2514.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/19\/2514\/48995397\/bioinformatics_25_19_2514.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:40:01Z","timestamp":1675201201000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/19\/2514\/182170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,12]]},"references-count":37,"journal-issue":{"issue":"19","published-print":{"date-parts":[[2009,10,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp486","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,10,1]]},"published":{"date-parts":[[2009,8,12]]}}}