New Algorithm Fills the Gaps in Evolutionary Distance Matrices with Tree-Aware Precision

Every evolutionary tree that scientists build from genetic data rests on a foundation of numbers. When researchers compare mitochondrial DNA sequences across species, they typically reduce the comparisons to a distance matrix, a grid in which each cell records how different two organisms are. Those matrices feed directly into distance-based phylogenetic methods that reconstruct the branching patterns of life. But real-world data are rarely complete. Sequences may be unavailable for some species, alignments may be ambiguous, and laboratory work may simply never have been done. The missing entries are not a trivial inconvenience: they can distort both the shape of the reconstructed tree and the estimated lengths of its branches, quietly changing the evolutionary story the data appear to tell.

A team of researchers led by Dmitrii Chaikovskii, Weilai Qu, Boris Melnikov, Ye Zhang, and Yuehong Zhao, working across Shenzhen MSU-BIT University, Beijing Institute of Technology, and Tsinghua University, has now introduced a new method designed to fill those gaps in a way that respects the special mathematics of evolutionary distances. The method, called Hyb-Adam-UA, short for hybrid Adam, ultrametrically initialized and additivity-aware, is described in a study published in BMC Bioinformatics. Rather than treating a phylogenetic distance matrix like any other incomplete table of numbers, the approach explicitly encourages the completed matrix to satisfy the structural properties that real trees impose on their distances.

The key insight behind the method lies in a classical piece of phylogenetic mathematics known as the four-point condition. For distances that genuinely come from a tree, the four-point condition holds: among the three sums of pairwise distances between any four taxa, the two largest sums are equal. A matrix that satisfies this additivity property can be perfectly represented by a tree. Generic matrix-completion methods, such as those based on low-rank assumptions or nearest-neighbor averaging, have no built-in reason to produce matrices with this structure. Hyb-Adam-UA closes that gap by optimizing a four-point additivity objective, pushing the filled-in values toward tree-like consistency while a triangle-inequality guard keeps the distances mathematically valid.

The method works in two distinct stages. In the first stage, the algorithm estimates the missing entries using minimax-path distances computed on the graph of observed values. Intuitively, this means the initial guess for an unknown distance between two species is derived from the least unfavorable chain of known distances connecting them through other species. This initialization is itself a strong completion strategy, and it draws on ultrametric ideas that echo classical clustering approaches. Crucially, the first stage never alters the distances that have actually been observed; it only fills in what is missing.

The second stage is where the tree-aware refinement comes in. Using the Adam optimizer, a popular adaptive gradient-based optimization algorithm from machine learning, the method adjusts only the previously missing entries to improve the four-point additivity score of the whole matrix, while the triangle-inequality guard prevents any entry from drifting into values that could not describe real distances. The observed distances remain fixed throughout. The result is a completed matrix that stays faithful to the data in hand but is nudged toward the kind of structure that phylogenetic interpretation expects, all without imposing a strict molecular-clock assumption that would force all lineages to evolve at the same rate.

To test the approach, the researchers constructed complete reference matrices from mitochondrial DNA alignments of primates. They used MAFFT multiple-sequence alignments and computed pairwise-deletion p-distances, a standard measure of sequence divergence. Two empirical benchmarks of fifteen species each were examined: one of closely related Cercopithecidae, the Old World monkey family, and one taxonomically heterogeneous primate dataset spanning a broader evolutionary range. Missingness was then simulated by masking entries at 30, 50, 65, and 85 percent, with thirty replicates at each level, and the true hidden values were used to score how well each method recovered them.

Hyb-Adam-UA was compared against a suite of established competitors, including MW-star-proj and NJ-star-proj, which project incomplete matrices onto the spaces of metrics and tree metrics respectively, as well as low-rank matrix completion, K-nearest-neighbor imputation, and multidimensional scaling with SMACOF. Evaluation covered four distinct criteria: the raw error on hidden entries, the accuracy of the reconstructed tree topology, the fidelity of patristic distances, meaning distances measured along the branches of the inferred tree, and the accuracy of estimated branch lengths. This multi-criteria design proved essential, because the study found that doing well on one criterion does not guarantee doing well on the others.

The results revealed a clear but nuanced picture. For the taxonomically heterogeneous primate dataset, the second-stage refinement significantly reduced the root-mean-square error on hidden entries compared with the first stage alone at 30, 50, and 65 percent missingness, and significantly outperformed MW-star-proj at 30, 65, and 85 percent missingness. Several branch-length estimates also improved. For the closely related Cercopithecidae dataset, however, the refinement offered no consistent advantage and was sometimes inferior to its own first-stage initialization, a finding the authors attribute to the strength of the minimax-path initialization itself, which can be hard to beat when species are closely related and distances are short and uniform in character.

Perhaps the most sobering conclusion concerns the relationship between matrix accuracy and tree accuracy. Improvements in hidden-entry reconstruction translated into only limited and inconsistent improvements in the recovered phylogenetic topology. In other words, a matrix that is numerically closer to the truth does not automatically yield a tree that is closer to the truth. The authors argue that matrix-level, branch-length, and topology criteria should therefore be evaluated separately in future work, a methodological warning with implications well beyond this single study, since many papers in the field report only one of these measures.

To probe whether the findings generalize beyond small empirical datasets, the team also ran a synthetic benchmark of thirty species with five replicates. Among the methods that succeeded in all five replicates, Hyb-Adam-UA achieved the lowest mean hidden-entry root-mean-square error at three of the four missingness levels and the lowest mean absolute error at all four, demonstrating that the additivity-aware framework scales beyond the fifteen-species empirical setting. The work, funded by the National Natural Science Foundation of China and several national and Shenzhen research programs, and supported by a granted Chinese invention patent on phylogenetic distance-matrix completion assigned to Shenzhen MSU-BIT University, offers evolutionary biologists a principled new tool: a way to complete fragmentary distance data that speaks the language of trees, while honestly acknowledging that a better-filled matrix is only one step toward a better tree.

Subject of Research: Additivity-aware completion of partially observed mitochondrial DNA phylogenetic distance matrices

Article Title: Hyb-Adam-UA: additivity-aware refinement of minimax-initialized mtDNA distance matrices

Article References: Chaikovskii, D., Qu, W., Melnikov, B., Zhang, Y., & Zhao, Y. (2026). Hyb-Adam-UA: additivity-aware refinement of minimax-initialized mtDNA distance matrices. BMC Bioinformatics. https://doi.org/10.1186/s12859-026-06629-3

Image Credits: AI Generated

DOI: 10.1186/s12859-026-06629-3

Keywords: mitochondrial DNA, distance matrix completion, phylogenetics, four-point condition, additive tree metrics, Adam optimizer, minimax-path distance, branch-length estimation, primates, BMC Bioinformatics, machine learning, ultrametric initialization