Related Experiment Video
Updated: Oct 6, 2025
06:38
Pattern-based Search of Epigenomic Data Using GeNemo
Published on: October 8, 2017
5.2K
MONI: A Pangenomic Index for Finding Maximal Exact Matches
Massimiliano Rossi1, Marco Oliva1, Ben Langmead2
1Department of Computer and Information Science and Engineering, University of Florida, Gainesville, Florida, USA.
Summary
We developed a new algorithm to efficiently find maximal exact matches (MEMs) in large genomic datasets. Our method, MONI, significantly reduces memory usage and speeds up index construction for repetitive sequences.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- The r-index, an efficient data structure for storing large genomes, has limitations for finding maximal exact matches (MEMs).
- Previous methods required separate steps to find thresholds, hindering efficient MEM identification.
Purpose of the Study:
- To develop a novel algorithm for simultaneous construction of the r-index and its associated thresholds.
- To enable efficient maximal exact match (MEM) finding in large, repetitive sequence collections.
Main Methods:
- Applied prefix-free parsing (PFP) to construct the r-index and identify thresholds concurrently.
- Developed an implementation named MONI for rapid MEM finding.
Main Results:
- MONI achieved linear time and space complexity relative to the prefix-free parse size.
- MONI demonstrated significant improvements over existing read aligners in memory usage (2-11x less) and index construction speed (2-32x faster).
- MONI's index size was drastically smaller (less than 1/1000th) for large human chromosome collections.
Conclusions:
- MONI offers a major advancement for efficient MEM finding in large, related reference genomes.
- The simultaneous PFP-based approach for r-index and threshold construction is highly effective.
Related Concept Videos
01:29Modern Molecular Taxonomy
234
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...
234
02:02Genomics
37.8K
Genomics is the science of genomes: it is the study of all the genetic material of an organism. In humans, the genome consists of information carried in 23 pairs of chromosomes in the nucleus, as well as mitochondrial DNA. In genomics, both coding and non-coding DNA is sequenced and analyzed. Genomics allows a better understanding of all living things, their evolution, and their diversity. It has a myriad of uses: for example, to build phylogenetic trees, to improve productivity and...
37.8K
02:54Evolutionary Relationships through Genome Comparisons
6.4K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
6.4K
02:51Multi-species Conserved Sequences
4.3K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
4.3K
01:33Proteomics
8.4K
A proteome is the entire set of proteins that a cell type produces. We can study proteomes using the knowledge of genomes because genes code for mRNAs, and the mRNAs encode proteins. Although mRNA analysis is a step in the right direction, not all mRNAs are translated into proteins.
Proteomics is the study of proteomes' function. It involves the large-scale systematic study of the proteome to denote the protein complement expressed by a genome. Scientist Mark Wilkins coined the term...
Proteomics is the study of proteomes' function. It involves the large-scale systematic study of the proteome to denote the protein complement expressed by a genome. Scientist Mark Wilkins coined the term...
8.4K
02:16Comparing Mitochondrial, Chloroplast, and Prokaryotic Genomes
14.4K
The present-day mitochondrial and chloroplast genomes have retained some of the characteristics of their ancestral prokaryotes and also have acquired new attributes during their evolution within eukaryotic cells. Like prokaryotic genomes, mitochondrial and chloroplast genomes neither bind with histone-like proteins nor show complex packaging into chromosome-like structures, as observed in eukaryotes. Unlike mitotic cell divisions observed in eukaryotic cells, mitochondria and chloroplasts...
14.4K