🧬 biology

Entropy-Driven Alignment-Free Phylogenetic Analysis via K-mer Encoding, DNA Physicochemical Properties, and Rough Set Feature Selection

This study proposes an alignment-free phylogenetic analysis framework that integrates k-mer statistics with DNA physicochemical properties and strand symmetry into a feature vector, which is then optimized using an enhanced rough set-based selection method to achieve efficient and interpretable whole-genome evolutionary inference.

Original authors: Yong Liu, Tongliang Xia, Xu Yan, He Wang, Xinyang Jiang, Shujie Gao, Shusheng Li, Yan Yang

Published 2026-08-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yong Liu, Tongliang Xia, Xu Yan, He Wang, Xinyang Jiang, Shujie Gao, Shusheng Li, Yan Yang

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

To understand the history of life, scientists often look at the molecular instructions written inside every living cell: the DNA sequence. For decades, the standard way to compare these instructions between different species has been to line them up side by side, letter by letter, much like aligning two long paragraphs of text to see where they match and where they differ. This method, known as multiple sequence alignment, works well when the sequences are short and very similar. However, as technology has advanced, researchers can now read entire genomes, which are millions of letters long. When these massive sequences are compared, especially among organisms that have shuffled their genetic material or evolved rapidly, the traditional alignment method becomes slow, computationally heavy, and sometimes impossible to perform accurately. This has led scientists to seek "alignment-free" methods, which try to find evolutionary relationships without forcing the sequences into a rigid line-up. Instead of matching every letter, these newer approaches look at the overall patterns and frequencies of small chunks of DNA to infer how closely related two organisms are.

In a recent study, a team of researchers from China proposed a new way to refine these alignment-free techniques to make them both faster and more accurate. They recognized that while many existing methods simply count how often certain short DNA patterns appear, they often miss two critical pieces of information: the specific chemical properties of the DNA building blocks and the order in which those patterns appear. To solve this, the researchers developed a system that translates a DNA sequence into a set of seven different "maps." Each map highlights a different physical characteristic of the DNA, such as whether a letter is part of a strong or weak chemical bond, or whether it belongs to a specific chemical family. By converting the original DNA sequence into these seven distinct binary patterns, they could then count the frequency of short word-like segments within each map. This process created a detailed, multi-layered profile of the genome that preserved both the chemical nature of the DNA and the specific order of its parts.

However, this detailed profile created a massive amount of data, containing thousands of potential patterns, many of which were redundant or unhelpful for determining evolutionary history. To cut through this noise, the team applied a mathematical strategy known as rough set theory. Think of this process as a highly efficient filter that sorts through a large pile of clues to find only the ones that actually help distinguish between different groups. The researchers tested this filtering system using a training set of eleven hantavirus strains, a type of virus found in East Asia. By analyzing how well different patterns could separate the viruses into their known types, the system identified a specific set of 3,005 patterns out of the original 14,336 possibilities. These selected patterns became the core "fingerprint" used to analyze the viruses.

The team then put their method to the test on three completely different groups of viruses to see if it could correctly reconstruct their family trees. First, they analyzed thirty-three coronavirus genomes, including the strains responsible for SARS and the more recent SARS-CoV-2. The method successfully grouped the viruses into four distinct branches that matched the known scientific classification, clearly separating the SARS-related viruses from the others and even distinguishing between the original SARS virus and the newer SARS-CoV-2. Next, they examined thirty-nine strains of the Japanese encephalitis virus. Again, the method correctly sorted the viruses into their four known genetic groups, mirroring the results obtained by traditional, much slower alignment methods. Finally, they analyzed fifty-five strains of the H7N9 avian influenza virus. The resulting tree showed two major lineages, one from North America and one from Eurasia, and correctly grouped viruses that were isolated in the same geographic regions and time periods.

Throughout these tests, the new approach proved to be remarkably fast. While other graphical methods for analyzing long DNA sequences can take several minutes, this method processed the longest sequences in the study, which were over 31,000 letters long, in just four seconds. The researchers noted that their approach does not require the complex and time-consuming step of aligning sequences, yet it still captures the essential biological signals needed to build accurate family trees. While the method is powerful, the authors acknowledge that it does not provide a visual picture of the differences between sequences in the way some other tools do, and it does not explicitly model complex genetic shuffling events. Nevertheless, the study demonstrates that by combining chemical properties with smart data filtering, scientists can create a tool that is both efficient and reliable for tracing the evolutionary history of viruses and other organisms across entire genomes.

Technical Summary: Entropy-Driven Alignment-Free Phylogenetic Analysis via K-mer Encoding, DNA Physicochemical Properties, and Rough Set Feature Selection

Problem Statement
The rapid expansion of whole-genome sequencing data has exposed significant limitations in traditional phylogenetic analysis, which relies heavily on multiple sequence alignment (MSA). MSA methods face bottlenecks regarding computational complexity, the arbitrariness of alignment penalties, and unsuitability for whole-genome scales due to genetic recombination, substitutions, and inversions. While alignment-free methods based on k-mers have emerged as efficient alternatives, existing approaches suffer from specific deficiencies: they primarily rely on nucleotide composition while neglecting the intrinsic physicochemical properties of DNA and the ordering information of k-mers. Furthermore, many methods fail to distinguish the varying contributions of different k-mers to evolutionary distance, leading to high-dimensional, redundant feature spaces that may obscure biologically meaningful signals.

Methodology
The authors propose a novel alignment-free framework that integrates k-mer statistics with DNA physicochemical properties and rough set theory for feature selection. The methodology proceeds through three main stages:

Seven-Characteristic Sequence Encoding:
Instead of treating DNA as a simple string of nucleotides, the method transforms a given DNA sequence into seven distinct binary (0,1) sequences based on physicochemical classifications:
- Purine/Pyrimidine (R/Y): {A, G} vs. {C, T}
- Keto/Amino (M/K): {A, C} vs. {G, T}
- Weak/Strong Hydrogen Bonds (W/S): {A, T} vs. {G, C}
- Single Nucleotide Contrast: Four additional sequences where each nucleotide (A, C, G, T) is assigned 0, and the other three are assigned 1.
For a specified k-mer length, the frequency of every possible k-mer is calculated for each of these seven sequences. To preserve sequential relationships, the frequency vectors are sorted in ascending order. A unique vector representation ( $V_F$ ) is then constructed for each binary sequence by combining the frequency values with their positional indices (rank) in the sorted vector. These seven vectors are concatenated to form a complete $7 \times 2^k$ -dimensional word vector representing the original DNA sequence.
Rough Set-Based Feature Selection:
To address the high dimensionality of the $7 \times 2^k$ vector (e.g., 14,336 dimensions for $k=11$ ), the authors employ an enhanced rough set-based feature selection method. This approach utilizes a decision table where the virus type serves as the decision attribute and the k-mer features serve as condition attributes.
- A novel attribute importance measure is introduced based on "folding points" and "average folding points" within ordered decision tables.
- The "minimum average folding point" ( $A_{mi}$ ) is calculated for each attribute. Attributes with higher $A_{mi}$ values are deemed more important for discrimination.
- This process heuristically selects a subset of the most informative k-mers, reducing redundancy while preserving classification ability.
Phylogenetic Inference:
Evolutionary distances between sequences are calculated using a formula that combines Euclidean distance and cosine similarity: $D(i, j) = d(v_i, v_j) / \cos(v_i, v_j)$ . Phylogenetic trees are subsequently constructed using the UPGMA method.

Key Results
The study evaluated the framework using four datasets: one training set and three independent test sets.

Training Phase (Hantaviruses): Using 11 Hantavirus S-segment sequences (5 HTN-type, 6 SEO-type), the optimal parameters were determined to be $k=11$ and a minimum average folding point threshold of 78.1866. From the initial 14,336 possible k-mers ( $7 \times 2^{11}$ ), 3,005 significant k-mers were selected. The resulting phylogenetic tree successfully distinguished between HTN-type and SEO-type viruses with strong branch support, matching the topology of alignment-based reference trees (ClustalW/MEGA).
Test Phase 1 (Coronaviruses): The 3,005 selected k-mers were applied to 33 complete coronavirus genomes. The method correctly clustered the viruses into four major groups (I, II, III, and IV), accurately separating SARS-related viruses (Group IV) from other groups and distinguishing between SARS-CoV and SARS-CoV-2 subclusters.
Test Phase 2 (Japanese Encephalitis Virus - JEV): Applied to 39 JEV genomes, the method successfully classified the viruses into four distinct genotypes (I, II, III, IV) consistent with established literature, using MVE-1-51 as an outgroup.
Test Phase 3 (H7N9 Influenza): Applied to 55 H7N9 NA gene sequences, the method resolved the viruses into North American and Eurasian lineages, with further clustering reflecting geographic and temporal proximity.

In all cases, the trees generated by the proposed method were topologically consistent with those generated by traditional alignment-based methods (ClustalW) and bootstrap analysis.

Computational Efficiency
The method demonstrated high computational efficiency. Processing the longest sequence in the study (31,100 bp) took less than 4 seconds on a standard consumer-grade CPU (Intel Core i5-10210U), contrasting with graphical representation methods reported in literature that require over 5 minutes for similar lengths.

Significance and Claims
The paper claims to provide an efficient and interpretable solution for whole-genome phylogenetic inference. Its primary significance lies in addressing the limitations of existing k-mer methods by:

Integrating physicochemical properties and sequence order through the seven-characteristic sequence encoding.
Utilizing rough set theory to perform dimensionality reduction that is specifically tailored to the discriminative power of k-mers, rather than relying on arbitrary frequency thresholds.
Demonstrating that this integrated approach can accurately reconstruct evolutionary relationships for diverse viral families (Hantavirus, Coronavirus, JEV, Influenza) without the computational burden of multiple sequence alignment.

The authors conclude that while the method does not offer the intuitive visual depiction of graphical methods and requires empirical tuning of parameters (k and feature size), it offers a robust, scalable framework for molecular phylogenetic analysis that captures essential evolutionary signals while maintaining computational speed.

More like this