16S rRNA metagenome clustering and diversity estimation using locality sensitive hashing

Area of Science:

• Microbiology
• Bioinformatics
• Computational Biology

Background:

• Metagenome sequencing decodes DNA from microbial communities in diverse environments.
• Metagenomics offers insights into ecosystem biodiversity and human health.
• Characterizing microbial populations is crucial in various scientific fields.

Purpose of the Study:

• To develop an efficient and scalable algorithm for species richness estimation in metagenomics.
• To improve the accuracy and speed of analyzing microbial community composition.
• To provide a tool for clinicians and researchers studying microbial ecosystems.

Main Methods:

• Developed a species richness estimation algorithm utilizing locality sensitive hashing (LSH).
• Approximated pairwise sequence comparisons using hashing for efficiency.
• Incorporated matching of fixed-length, gapless subsequences for enhanced comparison quality.
• Clustered similar sequences into operational taxonomic units (OTUs) using LSH-based similarity.

Main Results:

• The algorithm demonstrates efficiency and scalability in species richness estimation.
• LSH-based clustering yields meaningful operational taxonomic unit (OTU) assignments.
• The approach significantly reduces computational runtime compared to existing methods.
• Successfully applied the algorithm to analyze bacterial diversity across different skin locations.

Conclusions:

• The developed LSH-based algorithm is efficient and scalable for metagenomic analysis.
• It provides accurate OTU assignments and reduces computational runtime.
• The algorithm has practical significance for studying microbial diversity and structure in various environments, including the human body.