Graph construction in QUBO-based recursive phylogenetic tree reconstruction

• URL: http://arxiv.org/abs/2609.16640v1
• Date: Tue, 15 Sep 2026 05:00:33 GMT
• Title: Graph construction in QUBO-based recursive phylogenetic tree reconstruction
• Abstract summary: We evaluate sequence-to-affinity representations in a normalized-cut (Ncut) framework for phylogenetic reconstruction.<n> Affinity representation substantially affected internal split recovery, particularly for nucleotide data.<n>Post-swap refinement generally improved recovery, but not consistently across individual reconstructions.
• Score: 0.30586855806896046
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Molecular sequence data are used to reconstruct evolutionary relationships among taxa, but reconstruction accuracy depends not only on the tree-building method but also on how pairwise sequence relationships are represented. We evaluated sequence-to-affinity representations in a recursive normalized-cut (Ncut) framework whose graph-partitioning subproblems were formulated as quadratic unconstrained binary optimization (QUBO) models and solved using Simulated Bifurcation. Using simulated amino-acid and nucleotide datasets spanning multiple tree-generation settings and evolutionary divergence, we compared normalized bit-score affinities with representations derived from transformed sequence similarities and evolutionary distances, examined post-swap refinement, and used neighbor joining (NJ) as a distance-based comparator. Affinity representation substantially affected internal split recovery, particularly for nucleotide data. JC69-based local affinities maintained comparatively high accuracy as divergence increased, whereas normalized bit-score and BLAST-derived kernel representations declined more markedly. Post-swap refinement generally improved recovery, but not consistently across individual reconstructions. NJ achieved higher mean split recovery than corresponding recursive Ncut reconstructions for WAG and JC69 distances across all evaluated conditions, whereas recursive Ncut outperformed NJ for BLAST-derived logarithmic distances under some conditions. These results show that graph construction is an important determinant of recursive Ncut-based phylogenetic reconstruction. A representation that performs well within Ncut does not necessarily provide the most accurate use of the underlying pairwise distances. Pairwise representation, affinity transformation, optimization, and recursive tree construction should therefore be evaluated jointly.

Related papers

• Tree-Conditioned Edit Flows for Ancestral Sequence Reconstruction [0.0]
  Ancestral sequence reconstruction aims to infer extinct protein sequences at internal nodes of a phylogenetic tree.<n>We introduce a tree-conditioned edit-flow model for variable-length ASR.<n>On a benchmark of natural sequences with abundant insertions and deletions, the model most accurately localizes evolutionary change.
  arXiv  Detail & Related papers  (2026-05-05T13:04:45Z)
• Wave-Attractor-Tree: A Hierarchical Binary Tree Reduction Architecture for Efficient Sequence Modeling [0.0]
  Work introduces a hierarchical binary tree-based reduction that replaces standard self-attention.<n>The model significantly outperforms standard Transformers in both convergence speed and accuracy on long-range structural dependencies.
  arXiv  Detail & Related papers  (2026-02-28T21:17:27Z)
• PRISM: Parallel Residual Iterative Sequence Model [52.26239951489612]
  We propose PRISM (Parallel Residual Iterative Sequence Model) to resolve this tension.<n>PRISM introduces a solver-inspired inductive bias that captures key structural properties of multi-step refinement in a parallelizable form.<n>We prove that this formulation achieves Rank-$L$ accumulation, structurally expanding the update manifold beyond the single-step Rank-$1$ bottleneck.
  arXiv  Detail & Related papers  (2026-02-11T12:39:41Z)
• Hinge Regression Tree: A Newton Method for Oblique Regression Tree Splitting [18.562483381753804]
  We present the Hinge Regression Tree (HRT), which reframes each split as a non-linear least-squares problem over two linear predictors.<n>We analyze this node-level optimization and, for a backtracking line-search variant, prove that the local objective decreases monotonically and converges.<n>We show on synthetic and real-world benchmarks that HRT matches or outperforms single-tree baselines with more compact structures.
  arXiv  Detail & Related papers  (2026-02-05T06:49:01Z)
• RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees [2.612627266839037]
  Mixed-integer programming (MIP) has emerged as a powerful framework for learning optimal decision trees.<n>Naively binarizing continuous features sacrifices global optimality and often yields needlessly deep trees.<n>We recast the optimal regression-tree training as a two-stage optimization problem and propose Reduced-Space Optimal Regression Trees (RS-ORT)<n> RS-ORT is a specialized branch-and-bound (BB) algorithm that branches exclusively on tree-structural variables.
  arXiv  Detail & Related papers  (2025-10-27T22:17:09Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  We propose ReDiSC, a structured diffusion model for structured node classification.<n>We show that ReDiSC achieves superior or highly competitive performance compared to state-of-the-art GNN, label propagation, and diffusion-based baselines.<n> Notably, ReDiSC scales effectively to large-scale datasets on which previous structured diffusion methods fail due to computational constraints.
  arXiv  Detail & Related papers  (2025-07-19T04:46:53Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• PR-RRN: Pairwise-Regularized Residual-Recursive Networks for Non-rigid Structure-from-Motion [58.75694870260649]
  PR-RRN is a novel neural-network based method for Non-rigid Structure-from-Motion. We propose two new pairwise regularizations to further regularize the reconstruction. Our approach achieves state-of-the-art performance on CMU MOCAP and PASCAL3D+ dataset.
  arXiv  Detail & Related papers  (2021-08-17T08:39:02Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
  Spectral Top-Down Recovery (STDR) is a divide-and-conquer approach for inference of large latent tree models. STDR's partitioning step is non-random. Instead, it is based on the Fiedler vector of a suitable Laplacian matrix related to the observed nodes. We prove that STDR is statistically consistent, and bound the number of samples required to accurately recover the tree with high probability.
  arXiv  Detail & Related papers  (2021-02-26T02:47:42Z)
• Convolutional Ordinal Regression Forest for Image Ordinal Estimation [52.67784321853814]
  We propose a novel ordinal regression approach, termed Convolutional Ordinal Regression Forest or CORF, for image ordinal estimation. The proposed CORF integrates ordinal regression and differentiable decision trees with a convolutional neural network for obtaining precise and stable global ordinal relationships. The effectiveness of the proposed CORF is verified on two image ordinal estimation tasks, showing significant improvements and better stability over the state-of-the-art ordinal regression methods.
  arXiv  Detail & Related papers  (2020-08-07T10:41:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.