bioinformatics software developers

Abstract: Pangenomics uses graphs to show genetic differences within or between species. In these graphs, a path can represent one genome, while regions with different paths show genetic variation. Biedged graphs use black edges for sequences and grey edges for links between them. Snarls are minimal subgraphs of a biedged graph that are separated from the rest of the graph by removing two black edges. Ultrabubbles are minimal acyclic and tip-free snarls and thus are important variant structures because they have finite paths and lack dead ends. In our previous work, we showed that in linear time every bidirected graph can be transformed to a rooted biedged bipartite one, and that in these graphs, ultrabubbles can be enumerated with a lowest common ancestor (LCA)-based method in $O(Kn)$ time, where $n$ and $K$ are the number of nodes and given snarls, respectively, of the graph. Here, we present a series of practical and theoretical improvements to our previous LCA-based approach. First, we present a hybrid method that selects between the LCA-based method and the naive approach for evaluating a snarl, depending on the size of the snarl in relation to the number of tips and cycle-closing nodes in the graph. Second, by using the theoretical framework from our previous paper, we show that all ultrabubbles can be found in $O(n + m + K)$ time, where $m$ is the number of edges, by traversing the breadth-first search (BFS) tree of the biedged bipartite graph. Third, we show that any two snarls that are candidate ultrabubbles and share a frontier node cannot be ultrabubbles; the resulting set of snarls is compatible, bound by $n$, and defines exclusive families of nested snarls. We combine these three results into six methods and present benchmarking results that illustrate how the above improvements affect practical run-times for identifying ultrabubbles.

Abstract: The evolution of DNA sequences can be viewed as stochastic dynamics on a high-dimensional discrete space, but it is unclear when empirical transition biases reduce to an effective energy landscape versus retain irreducible non-equilibrium circulation. Human context-dependent mutation probabilities offer a direct test: every single-nucleotide substitution in a local context has a reverse substitution, so the logarithm of the forward-to-reverse probability ratio defines an antisymmetric field-the human mutation field. We show this field has a dominant gradient component and a smaller but reproducible curl component. Using seven-base human germline substitution probabilities, we infer an effective mutational landscape with a Siamese neural network constrained to predict only energy differences. This model predicts forward-to-reverse log-ratios for held-out mutations with a correlation of about 0.93, close to both an unconstrained predictive reference (0.948) and the empirical reversible ceiling from Hodge projection (about 0.96). Although trained only on mutation probabilities, the inferred landscape largely recovers short-word genomic composition and Chargaff reverse-complement symmetry for sequences up to length four. Deviations from equilibrium structure reveal a small but detectable nonequilibrium component: a residual irreversible circulation violating the Kolmogorov cycle condition for detailed balance, reproducible across African, Asian, and European populations, and strongest in CpG-linked cycles and CpG-transition edges, consistent with methylcytosine deamination. These results give a thermodynamic decomposition of the human mutation field: most mutation bias is organized by a local equilibrium-like energy landscape aligned with genome composition, while the residual circulation points to specific directional mutational mechanisms.