MONI

MONI identifies maximal exact matches (MEMs) between sequencing reads and large collections of genomic sequences by constructing an r-index with prefix-free parsing (PFP) to enable scalable MEM finding across highly repetitive reference collections.

Key Features:

• r-index (FM-index variant): MONI uses the r-index, an advanced version of the FM-index capable of storing thousands of human genomes on standard computing hardware.
• Prefix-free parsing (PFP) integration: MONI builds the r-index using prefix-free parsing to improve index construction efficiency.
• Threshold determination (Bannai et al.): MONI computes the thresholds introduced by Bannai et al. to enable effective MEM identification.
• Simultaneous construction: MONI integrates PFP to construct the r-index and determine thresholds in linear time and space relative to the size of the prefix-free parse.
• MEM identification: MONI rapidly identifies MEMs between reads and extensive sequence collections, including highly repetitive datasets.
• Memory efficiency: MONI requires 2–11× less memory than PuffAligner, Bowtie2, BWA-MEM, and CHIC.
• Construction speed: MONI builds indexes 2–32× faster than PuffAligner, Bowtie2, BWA-MEM, and CHIC.
• Compact index size: The MONI index is less than one thousandth the size of competing indexes for large human chromosome collections.

Scientific Applications:

• Large-scale MEM discovery: Identification of maximal exact matches between sequencing reads and large collections of genomic references.
• Analysis of highly repetitive references: MEM finding against extensive, highly repetitive sequence collections.
• Population-scale indexing: Indexing and querying thousands of human genomes and large human chromosome collections.

Methodology:

MONI integrates prefix-free parsing (PFP) to simultaneously construct the r-index and determine the thresholds of Bannai et al. in linear time and space relative to the size of the prefix-free parse; the r-index is an FM-index variant.