A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Every living thing carries a history written in its DNA, a molecular record of how populations have moved, mixed, and separated over thousands of years. For scientists, reconstructing this history is like trying to assemble a massive, fragmented puzzle where the pieces are genetic variations and the picture is the family tree of a species. One of the most reliable ways to trace human ancestry is by looking at the Y chromosome, a small piece of DNA passed down almost unchanged from father to son. Because it does not mix with DNA from the mother, the Y chromosome acts as a clear, unbroken line of descent, allowing researchers to map out the deep branches of the human family tree. However, as the amount of genetic data grows, the task of finding the correct tree structure becomes incredibly difficult. The number of possible ways to arrange even a modest number of people into a family tree is so vast that it exceeds the capacity of standard computers to check every possibility one by one. This combinatorial explosion has forced scientists to rely on shortcuts, or heuristics, which guess the best answer quickly but do not guarantee it is the true one.

A team of researchers at CRS4 in Sardinia has developed a new computational workflow that tackles this problem by combining two distinct strategies: breaking a giant problem into smaller, manageable pieces and using a specialized type of quantum-inspired algorithm to solve those pieces. Their work focuses on human Y-chromosome data, specifically looking at single-letter changes in the genetic code known as single nucleotide polymorphisms. The researchers started with a dataset containing genetic information from 150 samples, which they cleaned to remove 72 uninformative samples that lacked necessary genetic variants, leaving 78 male populations for analysis. They then used their new method to reconstruct the evolutionary tree. Instead of trying to solve the entire tree at once, which would be too complex for current technology, they split the task into two main decisions. First, they determined which groups of people should be clustered together on the tree. Second, they figured out where the very beginning of the tree, the root, should be placed to show the direction of time.

To make these decisions, the researchers translated the biological problem into a mathematical format known as a quadratic unconstrained binary optimization problem. In plain terms, this is a way of turning the search for the best tree into a game of finding the lowest point in a complex landscape of hills and valleys, where the lowest point represents the most likely family history. The challenge is that this landscape is too huge to explore all at once. The team's solution was to use a technique called ADMM decomposition, which divides the massive landscape into overlapping smaller sections. Each section is solved independently, and then the results are stitched back together to form a consistent whole. This allows the system to handle a problem size that would otherwise be impossible for a single computer to process.

For solving these smaller sections, the team employed a method called digitized counter-diabatic quantum optimization. This approach uses the principles of quantum mechanics to find the lowest point in the landscape very quickly. Unlike other quantum methods that require a slow, iterative process of trial and error, this technique calculates the path to the solution in a single, direct pass. The researchers tested their workflow on a noise-free computer simulation that mimics the behavior of a quantum processor. They found that the method successfully reconstructed the family tree of the 78 populations. The resulting tree placed the root deep within African lineages, a finding that aligns with established scientific understanding of human origins. Furthermore, while every grouping identified by their new method was consistent with a standard, widely accepted tree-building technique called Neighbor-Joining, the new method only recovered 40% of the groupings found in the Neighbor-Joining reference tree, indicating that while their approach is precise, it identified fewer total clusters than the standard method.

The study demonstrates that this hybrid approach, which combines splitting large problems with efficient quantum-style solvers, is a viable path forward for population genomics. It offers a way to move beyond the guesswork of traditional shortcuts without requiring the massive, error-prone hardware that full-scale quantum computers currently need. By proving that they can solve these difficult tree-reconstruction problems on a simulated quantum device, the researchers have shown that the technology is ready to be applied to even larger datasets in the future. Their work provides a clear, step-by-step pipeline that takes raw genetic data and turns it into a rooted, annotated family tree, complete with the specific genetic markers that define each branch. This achievement suggests that the field is moving toward a future where the full complexity of human evolutionary history can be mapped with greater precision and less reliance on approximation.