{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,26]],"date-time":"2023-01-26T05:20:08Z","timestamp":1674710408054},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"20","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Nucleic acid diagnostics has high demands for non-heuristic exact and approximate oligonucleotide string matching concerning in silico primer\/probe design in huge nucleic acid sequence collections. Unfortunately, public sequence repositories grow much faster than computer hardware performance and main memory capacity do. This growth imposes severe problems on existing oligonucleotide primer\/probe design applications necessitating new approaches based on space-efficient indexing structures.<\/jats:p>\n               <jats:p>Results: We developed PTPan (spoken Peter Pan, \u2018PT\u2019 is for Position Tree, the earlier name of suffix trees), a space-efficient indexing structure for approximate oligonucleotide string matching in nucleic acid sequence data. Based on suffix trees, it combines partitioning, truncation and a new suffix tree stream compression to deal with large amounts of aligned and unaligned data. PTPan operates efficiently in main memory and on secondary storage, balancing between memory consumption and runtime during construction and application. Based on PTPan, applications supporting similarity search and primer\/probe design have been implemented, namely FindFamily, ProbeMatch and ProbeDesign. All three use a weighted Levenshtein distance metric for approximative queries to find and rate matches with indels as well as substitutions.<\/jats:p>\n               <jats:p>We integrated PTPan in the worldwide used software package ARB to demonstrate usability and performance. Comparing PTPan and the original ARB index for the very large ssu-rRNA database SILVA, we recognized a shorter construction time, extended functionality and dramatically reduced memory requirements at the price of expanded, but very reasonable query times.<\/jats:p>\n               <jats:p>PTPan enables indexing of huge nucleic acid sequence collections at reasonable application response times. Not being limited by main memory, PTPan constitutes a major advancement regarding rapid oligonucleotide string matching in primer\/probe design now and in the future facing the enormous growth of molecular sequence data.<\/jats:p>\n               <jats:p>Availability: \u00a0Supplementary Material, PTPan stand-alone library and ARB-PTPan binary on http:\/\/ptpan.lrr.in.tum.de\/.<\/jats:p>\n               <jats:p>Contact: \u00a0meierh@in.tum.de<\/jats:p>\n               <jats:p>Supplementary Information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btr483","type":"journal-article","created":{"date-parts":[[2011,8,20]],"date-time":"2011-08-20T01:14:59Z","timestamp":1313802899000},"page":"2797-2805","source":"Crossref","is-referenced-by-count":3,"title":["PTPan\u2014overcoming memory limitations in oligonucleotide string matching for primer\/probe design"],"prefix":"10.1093","volume":"27","author":[{"given":"Tilo","family":"Ei\u00dfler","sequence":"first","affiliation":[{"name":"Chair of Computer Architecture, Department of Informatics, Technische Universit\u00e4t M\u00fcnchen, Boltzmannstrasse 3, 85748 Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher P.","family":"Hodges","sequence":"additional","affiliation":[{"name":"Chair of Computer Architecture, Department of Informatics, Technische Universit\u00e4t M\u00fcnchen, Boltzmannstrasse 3, 85748 Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harald","family":"Meier","sequence":"additional","affiliation":[{"name":"Chair of Computer Architecture, Department of Informatics, Technische Universit\u00e4t M\u00fcnchen, Boltzmannstrasse 3, 85748 Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2011,8,19]]},"reference":[{"key":"2023012512011844600_B1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Dis. Algorithms"},{"key":"2023012512011844600_B2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1038\/nrmicro1888","article-title":"Single-cell identification in microbial communities by improved fluorescence in situ hybridization techniques","volume":"6","author":"Amann","year":"2008","journal-title":"Nat. Rev. Microbiol."},{"key":"2023012512011844600_B3","doi-asserted-by":"crossref","first-page":"e6372","DOI":"10.1371\/journal.pone.0006372","article-title":"A method for studying protistan diversity using massively parallel sequencing of V9 hypervariable regions of small-subunit ribosomal RNA genes","volume":"4","author":"Amaral-Zettler","year":"2009","journal-title":"PLoS One"},{"key":"2023012512011844600_B4","doi-asserted-by":"crossref","first-page":"1546","DOI":"10.1093\/bioinformatics\/btr161","article-title":"Comprehensive and relaxed search for oligonucleotide signatures in hierarchically-clustered sequence datasets","volume":"26","author":"Bader","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012512011844600_B5","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1002\/spe.960","article-title":"A survey of practical algorithms for suffix tree construction in external memory","volume":"40","author":"Barsky","year":"2010","journal-title":"Softwr. Pract. Exp."},{"key":"2023012512011844600_B6","doi-asserted-by":"crossref","first-page":"5069","DOI":"10.1128\/AEM.03006-05","article-title":"Greengenes, a chimera-checked 16S rRNA gene database and workbench compatible with ARB","volume":"72","author":"DeSantis","year":"2006","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012512011844600_B7","article-title":"Distributed Data Structures for Efficient Molecular Sequence Analysis","volume-title":"Master's Thesis","author":"Hodges","year":"2003"},{"key":"2023012512011844600_B8","first-page":"91","article-title":"A method for the construction of minimum-redundancy codes","volume":"11","author":"Huffman","year":"1952","journal-title":"Proc. I.R.E."},{"key":"2023012512011844600_B9","doi-asserted-by":"crossref","first-page":"3825","DOI":"10.1128\/AEM.00260-10","article-title":"Analysis of the fine-scale population structure of \u2018Candidatus accumulibacter phosphatis\u2019 in enhanced biological phosphorus removal sludge, using fluorescence in situ hybridization and flow cytometric sorting","volume":"76","author":"Kim","year":"2010","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012512011844600_B10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1186\/1471-2105-6-61","article-title":"Graphical representation of ribosomal RNA probe accessibility data using ARB software package","volume":"6","author":"Kumar","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012512011844600_B11","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023012512011844600_B12","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":"2023012512011844600_B13","doi-asserted-by":"crossref","first-page":"2894","DOI":"10.1111\/j.1462-2920.2008.01706.x","article-title":"probeCheck - a central resource for evaluating oligonucleotide probe coverage and specificity","volume":"10","author":"Loy","year":"2008","journal-title":"Environ. Microbiol."},{"key":"2023012512011844600_B14","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1093\/nar\/gkh293","article-title":"ARB: a software environment for sequence data","volume":"32","author":"Ludwig","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012512011844600_B15","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1111\/j.1462-2920.2010.02306.x","article-title":"Non-target sites with single nucleotide insertions or deletions are frequently found in 16S rRNA sequences and can lead to false positives in fluorescence in situ hybridization (FISH)","volume":"13","author":"McIlroy","year":"2011","journal-title":"Environ. Microbiol."},{"key":"2023012512011844600_B16","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1007\/978-3-642-00887-0_63","article-title":"Reducing space requirements for disk resident suffix arrays","volume-title":"Database Systems for Advanced Applications","author":"Moffat","year":"2009"},{"key":"2023012512011844600_B17","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/978-3-642-16321-0_34","article-title":"CST++","volume-title":"String Processing and Information Retrieval","author":"Ohlebusch","year":"2010"},{"key":"2023012512011844600_B18","doi-asserted-by":"crossref","first-page":"e98","DOI":"10.1371\/journal.pcbi.0030098","article-title":"Comprehensive DNA signature discovery and validation","volume":"3","author":"Phillippy","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023012512011844600_B19","doi-asserted-by":"crossref","first-page":"7188","DOI":"10.1093\/nar\/gkm864","article-title":"SILVA: a comprehensive online resource for quality checked and aligned ribosomal RNA sequence data compatible with ARB","volume":"35","author":"Pruesse","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023012512011844600_B20","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.3390\/a2031105","article-title":"Approximate string matching with compressed indexes","volume":"2","author":"Russo","year":"2009","journal-title":"Algorithms"},{"key":"2023012512011844600_B21","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1111\/j.1462-2920.2008.01800.x","article-title":"16S rRNA gene-based phylogenetic microarray for simultaneous identification of members of the genus Burkholderia","volume":"11","author":"Sch\u00f6nmann","year":"2009","journal-title":"Environ. Microbiol."},{"key":"2023012512011844600_B22","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1504\/IJBRA.2008.017165","article-title":"The generalised k-truncated suffix tree for time-and space-efficient searches in multiple DNA or protein sequences","volume":"4","author":"Schulz","year":"2008","journal-title":"Int. J. Bioinformatics Res. Appl."},{"key":"2023012512011844600_B23","doi-asserted-by":"crossref","first-page":"2872","DOI":"10.1111\/j.1462-2920.2008.01719.x","article-title":"Systematic evaluation of single mismatch stability predictors for fluorescence in situ hybridization","volume":"10","author":"Yilmaz","year":"2008","journal-title":"Environ. Microbiol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/20\/2797\/48870392\/bioinformatics_27_20_2797.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/20\/2797\/48870392\/bioinformatics_27_20_2797.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T14:02:05Z","timestamp":1674655325000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/20\/2797\/202230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,19]]},"references-count":23,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2011,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btr483","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,10,15]]},"published":{"date-parts":[[2011,8,19]]}}}