PTPan--overcoming memory limitations in oligonucleotide string matching for primer/probe design

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Nucleic acid diagnostics requires efficient exact and approximate oligonucleotide matching for primer/probe design.
• Rapid growth of public sequence repositories outpaces hardware capabilities, challenging existing primer design tools.
• Need for novel, space-efficient indexing structures to manage large-scale nucleic acid sequence data.

Purpose of the Study:

• To develop a space-efficient indexing structure for approximate oligonucleotide string matching in large nucleic acid datasets.
• To enable efficient primer/probe design and similarity searches on rapidly growing sequence collections.
• To address the memory and computational limitations of existing bioinformatics tools.

Main Methods:

• Developed PTPan, a novel indexing structure based on suffix trees.
• Incorporated partitioning, truncation, and suffix tree stream compression for efficient data handling.
• Implemented weighted Levenshtein distance for approximate queries, including indels and substitutions.

Main Results:

• PTPan significantly reduces memory requirements compared to existing methods for large datasets like SILVA.
• Achieved shorter construction times and extended functionality when integrated into the ARB software package.
• Demonstrated efficient operation in both main memory and on secondary storage, balancing performance and resource usage.

Conclusions:

• PTPan enables effective indexing of massive nucleic acid sequence collections with reasonable response times.
• It overcomes main memory limitations, advancing rapid oligonucleotide string matching for primer/probe design.
• PTPan is a crucial advancement for future molecular sequence data analysis, accommodating exponential growth.