FSWM

FSWM identifies spaced-word matches and estimates nucleotide substitution frequencies to compute phylogenetic distances and reconstruct evolutionary relationships from genomic sequences.

Key Features:

• Alignment-free spaced-word matching: Uses a binary pattern of match and don't-care positions to identify spaced-word matches as gap-free local alignments with exact matches at match positions and allowed mismatches at don't-care positions.
• Substitution frequency estimation: Estimates the number of nucleotide substitutions per site by analyzing the nucleotides aligned at the don't-care positions of spaced-word matches for phylogenetic distance calculations.
• Noise reduction via filtering: Discards spaced-word matches whose overall similarity between aligned segments falls below a predefined threshold to reduce random matches and improve accuracy.
• Performance with distantly related sequences: Improves estimation of substitution frequencies for distantly related sequences, enabling phylogenetic inference where other alignment-free methods struggle.
• Efficiency on large genomes: Processes pairs of eukaryotic genomes of several hundred megabases in size within minutes for rapid distance estimation.

Scientific Applications:

• Phylogeny reconstruction: Computes substitution-based distances from spaced-word matches to support construction of phylogenetic trees.
• Comparative genomics: Enables rapid comparison of large genomic datasets without full alignments.
• Evolutionary biology: Facilitates analysis of evolutionary relationships, including among distantly related taxa.

Methodology:

Identify spaced-word matches using a binary match/don't-care pattern to produce gap-free local alignments, extract nucleotides at don't-care positions to estimate nucleotide substitutions per site, filter matches below a similarity threshold, and use the estimated substitution frequencies to compute phylogenetic distances.