Abstract
An approach of building phylogenetic trees is to define a distance function based on amino acid sequences of distinct proteins. The aim of this approach is to determine a weighted tree topology that approximates the entire functional similarity relations between proteins, defined by a distance function. In this case, the similarity relation has a symmetric property. However, the assumption of symmetry is not always appropriate, because non-symmetric similarity relations between proteins might have a biological significance. This notion inspired us to define a novel, compression-based, non-symmetric dissimilarity measure and to modify the ubiquitous 'Unweighted Pair Group Method with Arithmetic Mean' (UPGMA)-based tree-building algorithm so that the new measure can be applied.
Introduction
In phylogenetics, researchers typically build evolutionary trees based on the similarity between protein or DNA sequences. Standard methods like the Jukes-Cantor or Kimura models rely on two major assumptions: sequence alignment and symmetry. Sequence alignment often requires computationally expensive dynamic programming. Furthermore, these models assume the distance from protein A to protein B is identical to the distance from B to A.
However, symmetry isn't always biologically appropriate. One protein might contain more evolutionary "information" than another, making the relationship inherently directional. This paper introduces a novel way to build phylogenetic trees by abandoning the traditional assumption of symmetry and using an alignment-free method based on data compression.
Methodology
The researchers proposed a two-stage approach called Least Squares Unweighted Pair Group Method with Arithmetic Mean (LS-UPGMA).
Non-Symmetric Dissimilarity Measure (NSDM)
Instead of traditional distance formulas, an information-theoretic approach based on Kolmogorov complexity was used. Since true Kolmogorov complexity is uncomputable, it was approximated using the Lempel-Ziv compression algorithm. The measure $n(x,y)$ essentially asks: "How much new information does sequence $y$ add if we already know sequence $x$?" The formula used is: $$n(x,y) = \frac{C(xy) - C(x)}{C(xy)}$$ where $C(xy)$ is the compressed length of the concatenated sequences.
Modified UPGMA (MUPGMA) and Optimization
Standard UPGMA handles symmetric matrices. The authors modified it to determine tree topology by using the maximum of the two directional distances ($\max(d_{ij}, d_{ji})$) to decide which clusters to join. Once the tree topology (the branching structure) is set, they used a constrained least-squares numerical procedure to assign optimal weights to the edges, accounting for the directed nature of the distances.
Results and Classification
The method was tested on a biological dataset of 73 [NiFe] hydrogenase enzymes from various microorganisms (Archaea and Bacteria). These enzymes are crucial for microbial energy metabolism, and their classification is a complex problem in biology.
The algorithm successfully categorized the 73 hydrogenases into four distinct functional groups (Groups A, B, C, and D), largely aligning with and in some cases refining existing biological classifications.
Key findings from the resulting tree include:
- Group A Discovery: The identification of a specific group of $H_2$-evolving hydrogenases (Group-A) that were previously scattered or poorly defined in other models.
- Structural Reliability: Within the identified groups, the distance from the root was remarkably uniform. This internal consistency suggests the method provides a more robust taxonomic signal than previous approaches.
Discussion and Conclusion
By using compression, the authors bypass the "alignment bottleneck," which is a significant advantage for large datasets or highly divergent sequences where alignment is difficult. Treating evolution as an information-processing sequence allows for a "left-handed" and "right-handed" view of the same topology, where the path weights from the root to the leaves can differ depending on the direction of comparison.
While this method provides a strong heuristic, phylogenetic tree building remains NP-complete. Future work will explore different aggregation operators beyond the "max" operator and extend the algorithm to build multiple tree topologies simultaneously to better explore the vast solution space of possible evolutionary histories.
Summary updated