andi

andi estimates evolutionary distances between closely related genomes to enable rapid phylogenetic inference across large genomic datasets, such as thousands of bacterial genomes.

Key Features:

• Efficient distance calculation: andi calculates pairwise distances without requiring full sequence alignments, improving computational efficiency for large genome collections.
• Ungapped local alignments with MUMs: andi uses ungapped local alignments anchored by pairs of maximal unique matches (MUMs) with a specified minimum length, where exact matches distinguish homologous from non-homologous regions.
• Enhanced suffix arrays: andi leverages enhanced suffix arrays to efficiently locate MUMs, with reported performance of approximately 1 second and 45 MB RAM per megabase of sequence.
• Scalability: andi scales to thousands of genomes by avoiding full alignments, maintaining low computational demand for high-throughput studies.
• Multithreaded implementation: andi is implemented as a multithreaded UNIX program to enable parallel processing and improve performance on modern computing architectures.

Scientific Applications:

• Phylogenetic analysis: infer phylogenies for large sets of closely related genomes to resolve evolutionary relationships among species or strains.
• Population genomics: analyze genetic diversity and evolutionary dynamics in bacterial populations, including Escherichia coli and Streptococcus pneumoniae.
• Comparative genomics: distinguish homologous from non-homologous regions to identify conserved elements and genomic innovations.
• Validation and reliability: accuracy validated on simulated data and real-world datasets, including 29 Escherichia coli/Shigella genomes and 3085 Streptococcus pneumoniae genomes.

Methodology:

Calculates pairwise distances without full alignments using ungapped local alignments anchored by MUMs of specified minimum length, identifies MUMs via enhanced suffix arrays, and runs as a multithreaded program.