Lowest Common Ancestor (LCA) Algorithm

The LCA algorithm assigns a sequencing read to the deepest taxonomic node that is a common ancestor of all reference genomes with a significant alignment match. If a read aligns equally well to multiple species within a genus, the algorithm assigns it to the genus level rather than risking a false species call. This trade-off deliberately sacrifices strain-level resolution to maintain high precision in taxonomic profiling.

The algorithm operates on a pre-computed taxonomic tree where each node represents a taxonomic rank (species, genus, family, etc.). The process follows three steps:

• Step 1: Collect all reference genomes that have a significant alignment with the query read
• Step 2: Map each matched genome to its corresponding leaf node in the taxonomic tree
• Step 3: Traverse upward from all matched leaves until a single common ancestor node is found

The read is assigned the taxID of that common ancestor node.

The LCA approach explicitly optimizes for high precision at the cost of reduced sensitivity at lower taxonomic ranks. Key performance characteristics include:

• Precision: Typically exceeds 95% at genus level and above
• Sensitivity: Lower than abundance-based profilers like MetaPhlAn for species-level detection
• False Positive Rate: Near zero for well-represented clades in the reference database
• Ambiguous Reads: Reads from conserved genomic regions (e.g., 16S rRNA) are often assigned to higher ranks like family or order

A core strength of the LCA algorithm is its graceful degradation when reads map to multiple reference genomes. Scenarios include:

• Conserved genes: Ribosomal proteins and tRNA synthetases that are nearly identical across genera result in family-level assignments
• Horizontal gene transfer: Recently transferred genes may map to distantly related taxa, causing assignment to phylum or domain level
• Incomplete references: If a species is absent from the database, reads may map to a sister species, and the LCA correctly assigns to the shared genus node This behavior prevents the false novelty calls that plague best-hit-only classifiers.

Building an LCA reference database requires a complete taxonomic tree and representative genomes for each node. The construction process:

• Taxonomy: Uses NCBI Taxonomy or GTDB as the backbone hierarchical structure
• Genome Selection: Curated reference and representative genomes are downloaded for each species
• k-mer Indexing: Each genome is decomposed into overlapping k-mers (default k=35 for Kraken2)
• LCA Pre-computation: For each k-mer, the LCA taxID across all genomes containing that k-mer is stored
• Compact Representation: Uses minimizer-based downsampling to reduce database size by 10-100x without significant accuracy loss