PAC

PAC implements an approximate membership query (AMQ) data structure to index and query very large sequence collections for rapid detection of small sequence signatures and variants.

Key Features:

• Approximate Membership Query (AMQ) data structure: PAC_seq employs a novel AMQ data structure optimized for querying extensive sequence datasets efficiently.
• Scalability and construction speed: Achieves 3–6 fold faster index building compared to other compressed methods while maintaining comparable index sizes.
• Streaming index construction: Constructs the index in a streaming fashion, processing data sequentially with no additional disk footprint beyond the index itself.
• Query performance: Performs queries in constant time under favorable conditions, requiring only a single random access operation.
• Large-scale indexing capability: Indexed 32,000 human RNA-seq samples in five days and the entire GenBank bacterial genome collection in one day, producing a 3.5 TB index and representing the largest sequence collection indexed with an AMQ structure to date.
• High-throughput queries: Can query up to 500,000 transcript sequences in less than an hour.

Scientific Applications:

• Large-scale genomic and transcriptomic searches: Indexes and searches vast collections such as RNA-seq datasets and GenBank bacterial genomes for presence/absence of sequences.
• Comparative genomics: Enables rapid detection of small signatures or variants across many genomes or transcriptomes.
• Metagenomics: Supports querying large bacterial genome collections for taxonomic or functional sequence signatures.
• Personalized medicine and variant screening: Facilitates rapid lookup of sequence variants or small signatures across extensive sequence repositories.

Methodology:

PAC uses a novel AMQ data structure, constructs its index in a streaming fashion, and supports constant-time queries that require only single random access operations.