SeqDistK

SeqDistK computes alignment-free k-mer based sequence dissimilarities and constructs phylogenetic trees for large-scale metagenomic and 16S rRNA datasets.

Key Features:

• Alignment-Free Approach: Implements an alignment-free methodology to quantify sequence differences without multiple sequence alignment, suitable for large metagenomic datasets.
• Dissimilarity Matrix Computation: Computes dissimilarity matrices using seven k-mer based measures: d2, d2S, d2star, Euclidean, Manhattan, CVTree, and Chebyshev.
• Phylogenetic Tree Construction: Constructs phylogenetic trees using the Unweighted Pair Group Method with Arithmetic Mean (UPGMA) algorithm from the computed dissimilarity matrices.
• Performance and Accuracy: On a 16S rRNA golden-standard dataset, demonstrated ~38-fold faster computation than Muscle while producing trees with smaller symmetric differences to the ground truth.
• Clustering Consistency: Achieved optimal taxonomic classification using the d2S measure with parameters k=5 and M=2, correctly grouping sample sequences by known taxonomy.

Scientific Applications:

• Microbial Evolution: Inference of evolutionary relationships among viruses and bacteria using large-scale sequence data.
• Metagenomics: Phylogenetic analysis and distance-based clustering of metagenomic sequence datasets.
• Evolutionary Biology: Reconstruction and comparison of phylogenetic trees for evolutionary studies.
• Microbial Community Analysis: Exploration of complex microbial communities and elucidation of their evolutionary histories using alignment-free distance measures.

Methodology:

Computes k-mer based dissimilarity matrices (d2, d2S, d2star, Euclidean, Manhattan, CVTree, Chebyshev), constructs phylogenetic trees with UPGMA, and evaluates performance against Muscle on a 16S rRNA gold-standard dataset using computation time and symmetric difference metrics; example parameterization includes d2S with k=5 and M=2.