Pangenome-guided sequence assembly via binary optimisation

• URL: http://arxiv.org/abs/2508.08200v1
• Date: Mon, 11 Aug 2025 17:17:21 GMT
• Title: Pangenome-guided sequence assembly via binary optimisation
• Abstract summary: We propose a framework for pangenome-guided sequence assembly.<n>It can resolve short-read data in complex regions without bias towards a single reference genome.<n>Our method frames assembly as a graph optimisation problem, which can be implemented on quantum computers.
• Score: 0.040993632551842324
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: De novo genome assembly is challenging in highly repetitive regions; however, reference-guided assemblers often suffer from bias. We propose a framework for pangenome-guided sequence assembly, which can resolve short-read data in complex regions without bias towards a single reference genome. Our method frames assembly as a graph traversal optimisation problem, which can be implemented on quantum computers. The pipeline first annotates pangenome graphs with estimated copy numbers for each node, then finds a path on the graph that best explains those copy numbers. On simulated data, our approach significantly reduces the number of contigs compared to de novo assemblers. While it introduces a small increase in inaccuracies, such as false joins, our optimisation-based methods are competitive with current exhaustive search techniques. They are also designed to scale more efficiently as the problem size grows and will run effectively on future quantum computers.

Related papers

• From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs [6.381561491422844]
  We propose a generic, modular framework for processing heterogeneous nodes in branch and bound (BnB)<n>The framework is built around a small set of GPU-efficient routines and uses padding together with lightweight custom kernels to handle irregular node data structures.<n>Experiments show one to two orders of magnitude speedups and zero optimality gap on challenging instances.
  arXiv  Detail & Related papers  (2026-05-21T08:56:15Z)
• Learning Minimally Rigid Graphs with High Realization Counts [21.481970640320856]
  For rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations)<n>Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory.<n>We propose a reinforcement-learning approach that constructs minimally rigid graphs via 0- and 1-extensions, also known as Henneberg moves.
  arXiv  Detail & Related papers  (2026-05-12T17:23:30Z)
• Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly [0.42970700836450487]
  We develop near-term quantum optimisation approaches for genome assembly problems.<n>We use the Iterative-QAOA framework, which combines a fixed linear-ramp QAOA schedule with iterative warm-start bias updates.<n>A custom circuit compilation strategy reduces hardware gate overhead by up to 67% compared with standard tools.
  arXiv  Detail & Related papers  (2026-04-07T17:17:34Z)
• Encoding computationally hard problems in triangular Rydberg atom arrays [2.418500182135797]
  Rydberg atom arrays are a promising platform for quantum optimization.<n>We develop an encoding scheme that can universally encode computationally hard problems on triangular lattices.
  arXiv  Detail & Related papers  (2025-10-29T07:56:14Z)
• Finding trail covers: near-optimal decompositions of graph states as linear fusion networks [1.7842332554022695]
  We study three graph-theoretic problems which can be seen as generalisations of the Eulerian and Hamiltonian path problems.<n>These arise in photonic implementations of measurement-based quantum computing.<n>We propose new rewrite strategies for graph states that reduce the number of fusions required to build a given graph.
  arXiv  Detail & Related papers  (2025-08-25T18:06:53Z)
• Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach [0.5497663232622965]
  We discuss the complexity-theoretic limits of reductions from arbitrary graphs to unit-disk instances.<n>We prove any such reduction incurs a blow-up in geometric count and degrades solution approximation guarantees.<n>As a practical alternative, we propose a divide-and-conquer with only linear overhead which leverages pred atomic layouts.
  arXiv  Detail & Related papers  (2025-08-08T08:50:29Z)
• GraSSRep: Graph-Based Self-Supervised Learning for Repeat Detection in Metagenomic Assembly [24.55141372357102]
  Repetitive DNA (repeats) poses significant challenges for accurate and efficient genome assembly and sequence alignment. GraSSRep is a self-supervised learning framework to classify DNA sequences into repetitive and non-repetitive categories. GraSSRep combines sequencing features with pre-defined and learned graph features to achieve state-of-the-art performance in repeat detection.
  arXiv  Detail & Related papers  (2024-02-14T18:26:58Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Neural Topological Ordering for Computation Graphs [23.225391263047364]
  We propose an end-to-end machine learning based approach for topological ordering using an encoder-decoder framework. We show that our model outperforms, or is on-par, with several topological ordering baselines while being significantly faster on synthetic graphs with up to 2k nodes.
  arXiv  Detail & Related papers  (2022-07-13T00:12:02Z)
• Learning to Untangle Genome Assembly with Graph Convolutional Networks [17.227634756670835]
  We introduce a new learning framework to train a graph convolutional network to resolve assembly graphs by finding a correct path through them. Experimental results show that a model, trained on simulated graphs generated solely from a single chromosome, is able to remarkably resolve all other chromosomes.
  arXiv  Detail & Related papers  (2022-06-01T04:14:25Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• A step towards neural genome assembly [0.0]
  We train the MPNN model with max-aggregator to execute several algorithms for graph simplification. We show that the algorithms were learned successfully and can be scaled to graphs of sizes up to 20 times larger than the ones used in training.
  arXiv  Detail & Related papers  (2020-11-10T10:12:19Z)

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.