Amordad

Amordad implements alignment-free, content-based indexing within a geometric nearest-neighbor framework to compare metagenomic datasets and enable scalable similarity queries that bypass assembly and operational taxonomic unit (OTU) limitations caused by genetic variability and horizontal gene transfer.

Key Features:

• Alignment-Free Comparison: Utilizes a geometric framework for alignment-free comparison of metagenomic samples, eliminating the need for sequence alignment.
• Content-Based Indexing: Maps metagenomes as points in high-dimensional space to index datasets by content rather than taxonomic classifications.
• Geometric Contextualization: Combines random hashing with a regular nearest neighbor graph to frame metagenomic comparison in a geometric context.
• Efficient Query Performance: Encodes the effects of random hash functions within the nearest neighbor graph to achieve logarithmic query times for identifying similar metagenomes as the database scales to millions of entries.
• Scalability and Refinement: Supports continual database refinement through successive random hash applications, leveraging accumulated randomness without explicit maintenance of hash functions.

Scientific Applications:

• Microbial Ecology: Compare community composition and similarity across environmental samples at large scale using alignment-free signatures.
• Environmental Genomics: Survey and compare metagenomes from diverse environments to assess microbial diversity and function across ecosystems.
• Evolutionary Biology: Investigate genetic variability and the impact of horizontal gene transfer on community similarity without relying on assembly or OTU clustering.

Methodology:

Random hashing to generate sequence signatures; regular nearest neighbor graphs to organize points in high-dimensional space for efficient indexing and querying; and dynamic refinement via successive application of random hash functions with their effects encoded in the graph.