title: PTPan--overcoming memory limitations in oligonucleotide string matching for primer/probe design.
abstract: BACKGROUND
  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.
  
  
  RESULTS
  We developed PTPan (spoken Peter Pan, 'PT' 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. 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. 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.
  
  
  BACKGROUND
  Supplementary Material, PTPan stand-alone library and ARB-PTPan binary on http://ptpan.lrr.in.tum.de/.
  
  
  BACKGROUND
  meierh@in.tum.de
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Informatics, Technische Universität München, Boltzmannstrasse 3, 85748 Garching, Germany.
authors.forename: Tilo
authors.initials: T
authors.lastname: Eissler
authors.forename: Christopher P
authors.initials: CP
authors.lastname: Hodges
authors.forename: Harald
authors.initials: H
authors.lastname: Meier
mesh_terms: D000465:Algorithms; D017931:DNA Primers / Q000737:chemistry*; D015345:Oligonucleotide Probes / Q000737:chemistry*; D017422:Sequence Analysis, DNA; D017423:Sequence Analysis, RNA; D012984:Software
chemical_list: D017931:DNA Primers; D015345:Oligonucleotide Probes