Search

Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoretical advances exploit this idea to obtain algorithms parameterized by the number of paths of an MPC, known as the width. These results obtain fast [M\"akinen et al., TALG] and even linear time [C\'aceres et al., SODA 2022] algorithms in the small-width regime. In this paper, we present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders-of-magnitude.

We study the problem of finding maximal exact matches (MEMs) between a query string $Q$ and a labeled graph $G$. MEMs are an important class of seeds, often used in seed-chain-extend type of practical alignment methods because of their strong connections to classical metrics. A principled way to speed up chaining is to limit the number of MEMs by considering only MEMs of length at least $\kappa$ ($\kappa$-MEMs). However, on arbitrary input graphs, the problem of finding MEMs cannot be solved in truly sub-quadratic time under SETH (Equi et al., ICALP 2019) even on acyclic graphs. In this paper we show an $O(n\cdot L \cdot d^{L-1} + m + M_{\kappa,L})$-time algorithm finding all $\kappa$-MEMs between $Q$ and $G$ spanning exactly $L$ nodes in $G$, where $n$ is the total length of node labels, $d$ is the maximum degree of a node in $G$, $m = |Q|$, and $M_{\kappa,L}$ is the number of output MEMs. We use this algorithm to develop a $\kappa$-MEM finding solution on indexable Elastic Founder Graphs (Equi et al., Algorithmica 2022) running in time $O(nH^2 + m + M_\kappa)$, where $H$ is the maximum number of nodes in a block, and $M_\kappa$ is the total number of $\kappa$-MEMs. Our results generalize to the analysis of multiple query strings (MEMs between $G$ and any of the strings). Additionally, we provide some preliminary experimental results showing that the number of graph MEMs is an order of magnitude smaller than the number of string MEMs of the corresponding concatenated collection., Comment: 21 pages, 3 figures. To be published in the proceedings of WABI 2023. This article supersedes part of arXiv:2302.01748

Wheeler nondeterministic finite automata (WNFAs) were introduced as a generalization of prefix sorting from strings to labeled graphs. WNFAs admit optimal solutions to classic hard problems on labeled graphs and languages. The problem of deciding whether a given NFA is Wheeler is known to be NP-complete. Recently, however, Alanko et al. showed how to side-step this complexity by switching to preorders: letting $Q$ be the set of states, $E$ the set of transitions, $|Q|=n$, and $|E|=m$, they provided a $O(mn^2)$-time algorithm computing a totally-ordered partition of the WNFA's states such that (1) equivalent states recognize the same regular language, and (2) the order of non-equivalent states is consistent with any Wheeler order, when one exists. Then, the output is a preorder of the states as useful for pattern matching as standard Wheeler orders. Further research generalized these concepts to arbitrary NFAs by introducing co-lex partial preorders: any NFA admits a partial preorder of its states reflecting the co-lex order of their accepted strings; the smaller the width of such preorder is, the faster regular expression matching queries can be performed. To date, the fastest algorithm for computing the smallest-width partial preorder on NFAs runs in $O(m^2+n^{5/2})$ time, while on DFAs the same can be done in $O(\min(n^2\log n,mn))$ time. In this paper, we provide much more efficient solutions to the problem above. Our results are achieved by extending a classic algorithm for the relational coarsest partition refinement problem to work with ordered partitions. Specifically, we provide a $O(m\log n)$-time algorithm computing a co-lex total preorder when the input is a WNFA, and an algorithm with the same time complexity computing the smallest-width co-lex partial order of any DFA. Also, we present implementations of our algorithms and show that they are very efficient in practice.

A minimum chain cover (MCC) of a $k$-width directed acyclic graph (DAG) $G = (V, E)$ is a set of $k$ chains (paths in the transitive closure) of $G$ such that every vertex appears in at least one chain in the cover. The state-of-the-art solutions for MCC run in time $\tilde{O}(k(|V|+|E|))$ [M\"akinen et at., TALG], $O(T_{MF}(|E|) + k|V|)$, $O(k^2|V| + |E|)$ [C\'aceres et al., SODA 2022], $\tilde{O}(|V|^{3/2} + |E|)$ [Kogan and Parter, ICALP 2022] and $\tilde{O}(T_{MCF}(|E|) + \sqrt{k}|V|)$ [Kogan and Parter, SODA 2023], where $T_{MF}(|E|)$ and $T_{MCF}(|E|)$ are the running times for solving maximum flow (MF) and minimum-cost flow (MCF), respectively. In this work we present an algorithm running in time $O(T_{MF}(|E|) + (|V|+|E|)\log{k})$. By considering the recent result for solving MF [Chen et al., FOCS 2022] our algorithm is the first running in almost linear time. Moreover, our techniques are deterministic and derive a deterministic near-linear time algorithm for MCC if the same is provided for MF. At the core of our solution we use a modified version of the mergeable dictionaries [Farach and Thorup, Algorithmica], [Iacono and \"Ozkan, ICALP 2010] data structure boosted with the SIZE-SPLIT operation and answering queries in amortized logarithmic time, which can be of independent interest.

We show how to chain maximal exact matches (MEMs) between a query string $Q$ and a labeled directed acyclic graph (DAG) $G=(V,E)$ to solve the longest common subsequence (LCS) problem between $Q$ and $G$. We obtain our result via a new symmetric formulation of chaining in DAGs that we solve in $O(m+n+k^2|V| + |E| + kN\log N)$ time, where $m=|Q|$, $n$ is the total length of node labels, $k$ is the minimum number of paths covering the nodes of $G$ and $N$ is the number of MEMs between $Q$ and node labels, which we show encode full MEMs., Comment: 17 pages, 2 figures

Many important problems in Bioinformatics (e.g., assembly or multi-assembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding safe partial solutions (e.g., contigs) which are common to all solutions. Previous research on safety has focused on polynomially-time solvable problems, whereas many successful and natural models are NP-hard to solve, leaving a lack of "safety tools" for such problems. We propose the first method for computing all safe solutions for an NP-hard problem, minimum flow decomposition. We obtain our results by developing a "safety test" for paths based on a general Integer Linear Programming (ILP) formulation. Moreover, we provide implementations with practical optimizations aimed to reduce the total ILP time, the most efficient of these being based on a recursive group-testing procedure. Results: Experimental results on the transcriptome datasets of Shao and Kingsford (TCBB, 2017) show that all safe paths for minimum flow decompositions correctly recover up to 90% of the full RNA transcripts, which is at least 25% more than previously known safe paths, such as (Caceres et al. TCBB, 2021), (Zheng et al., RECOMB 2021), (Khan et al., RECOMB 2022, ESA 2022). Moreover, despite the NP-hardness of the problem, we can report all safe paths for 99.8% of the over 27,000 non-trivial graphs of this dataset in only 1.5 hours. Our results suggest that, on perfect data, there is less ambiguity than thought in the notoriously hard RNA assembly problem. Availability: https://github.com/algbio/mfd-safety

The problem of String Matching to Labeled Graphs (SMLG) asks to find all the paths in a labeled graph $G = (V, E)$ whose spellings match that of an input string $S \in \Sigma^m$. SMLG can be solved in quadratic $O(m|E|)$ time [Amir et al., JALG], which was proven to be optimal by a recent lower bound conditioned on SETH [Equi et al., ICALP 2019]. The lower bound states that no strongly subquadratic time algorithm exists, even if restricted to directed acyclic graphs (DAGs). In this work we present the first parameterized algorithms for SMLG in DAGs. Our parameters capture the topological structure of $G$. All our results are derived from a generalization of the Knuth-Morris-Pratt algorithm [Park and Kim, CPM 1995] optimized to work in time proportional to the number of prefix-incomparable matches. To obtain the parameterization in the topological structure of $G$, we first study a special class of DAGs called funnels [Millani et al., JCO] and generalize them to $k$-funnels and the class $ST_k$. We present several novel characterizations and algorithmic contributions on both funnels and their generalizations.

A minimum path cover (MPC) of a directed acyclic graph (DAG) $G = (V,E)$ is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size $k$ of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose running time is parameterized on $k$. We obtain a new MPC parameterized algorithm for DAGs running in time $O(k^2|V| + |E|)$. Our algorithm is the first solving the problem in parameterized linear time. Additionally, we obtain an edge sparsification algorithm preserving the width of a DAG but reducing $|E|$ to less than $2|V|$. This algorithm runs in time $O(k^2|V|)$ and requires an MPC of a DAG as input, thus its total running time is the same as the running time of our MPC algorithm., Comment: arXiv admin note: substantial text overlap with arXiv:2107.05717

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation $X$ on a directed graph $G$ into weighted source-to-sink paths whose superposition equals $X$. We show that, for acyclic graphs, considering the \emph{width} of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of \emph{width-stable} graphs, for which a popular heuristic is a \gwsimple-approximation ($|X|$ being the total flow of $X$), and strengthen its worst-case approximation ratio from $\Omega(\sqrt{m})$ to $\Omega(m / \log m)$ for sparse graphs, where $m$ is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a $(\lceil \log \Vert X \Vert \rceil +1)$-approximation ($\Vert X \Vert$ being the maximum absolute value of $X$ on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations ($\Vert X \Vert \leq 1$), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ALENEX 2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version., Comment: A preliminary version was submitted to ESA 2022

Decomposing a network flow into weighted paths has numerous applications. Some applications require any decomposition that is optimal w.r.t. some property such as number of paths, robustness, or length. Many bioinformatic applications require a specific decomposition where the paths correspond to some underlying data that generated the flow. For real inputs, no optimization criteria guarantees to uniquely identify the correct decomposition. Therefore, we propose to report safe paths, i.e., subpaths of at least one path in every flow decomposition. Ma, Zheng, and Kingsford [WABI 2020] addressed the existence of multiple optimal solutions in a probabilistic framework, i.e., non-identifiability. Later [RECOMB 2021], they gave a quadratic-time algorithm based on a global criterion for solving a problem called AND-Quant, which generalizes the problem of reporting whether a given path is safe. We give the first local characterization of safe paths for flow decompositions in directed acyclic graphs (DAGs), leading to a practical algorithm for finding the complete set of safe paths. We evaluated our algorithms against the trivial safe algorithms (unitigs, extended unitigs) and the popularly used heuristic (greedy-width) for flow decomposition on RNA transcripts datasets. Despite maintaining perfect precision our algorithm reports significantly higher coverage ($\approx 50\%$ more) than trivial safe algorithms. The greedy-width algorithm though reporting a better coverage, has significantly lower precision on complex graphs. Overall, our algorithm outperforms (by $\approx 20\%$) greedy-width on a unified metric (F-Score) when the dataset has significant number of complex graphs. Moreover, it has superior time ($3-5\times$) and space efficiency ($1.2-2.2\times$), resulting in a better and more practical approach for bioinformatics applications of flow decomposition., Comment: RECOMB 2022. arXiv admin note: text overlap with arXiv:2102.06480

A minimum path cover (MPC) of a directed acyclic graph (DAG) $G = (V,E)$ is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size $k$ of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose complexity is parameterized on $k$. We obtain two new MPC parameterized algorithms for DAGs running in time $O(k^2|V|\log{|V|} + |E|)$ and $O(k^3|V| + |E|)$. We also obtain a parallel algorithm running in $O(k^2|V| + |E|)$ parallel steps and using $O(\log{|V|})$ processors (in the PRAM model). Our latter two algorithms are the first solving the problem in parameterized linear time. Finally, we present an algorithm running in time $O(k^2|V|)$ for transforming any MPC to another MPC using less than $2|V|$ distinct edges, which we prove to be asymptotically tight. As such, we also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms. At the core of all our algorithms we interleave the usage of three techniques: transitive sparsification, shrinking of a path cover, and the splicing of a set of paths along a given path.

The width $k$ of a directed acyclic graph (DAG) $G = (V, E)$ equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth's and Fulkerson's results in the 1950s, and is doable in quadratic time in the worst case. Since $k$ can be small in practical applications, research has also studied algorithms whose complexity is parameterized on $k$. Despite these efforts, it is still open whether there exists a linear-time $O(f(k)(|V| + |E|))$ parameterized algorithm computing the width. We answer this question affirmatively by presenting an $O(k^24^k|V| + k2^k|E|)$ time algorithm, based on a new notion of frontier antichains. As we process the vertices in a topological order, all frontier antichains can be maintained with the help of several combinatorial properties, paying only $f(k)$ along the way. The fact that the width can be computed by a single $f(k)$-sweep of the DAG is a new surprising insight into this classical problem. Our algorithm also allows deciding whether the DAG has width at most $w$ in time $O(f(\min(w,k))(|V|+|E|))$.

We describe indexes for searching large data sets for variable-length-gapped (VLG) patterns. VLG patterns are composed of two or more subpatterns, between each adjacent pair of which is a gap-constraint specifying upper and lower bounds on the distance allowed between subpatterns. VLG patterns have numerous applications in computational biology (motif search), information retrieval (e.g., for language models, snippet generation, machine translation) and capture a useful subclass of the regular expressions commonly used in practice for searching source code. Our best approach provides search speeds several times faster than prior art across a broad range of patterns and texts., Comment: This research is supported by Academy of Finland through grant 319454 and has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941

Suffix trees are a fundamental data structure in stringology, but their space usage, though linear, is an important problem for its applications. We design and implement a new compressed suffix tree targeted to highly repetitive texts, such as large genomic collections of the same species. Our suffix tree tree builds on Block Trees, a recent Lempel-Ziv-bounded data structure that captures the repetitiveness of its input. We use Block Trees to compress the topology of the suffix tree, and augment the Block Tree nodes with data that speeds up suffix tree navigation. Our compressed suffix tree is slightly larger than previous repetition-aware suffix trees based on grammars, but outperforms them in time, often by orders of magnitude. The component that represents the tree topology achieves a speed comparable to that of general-purpose compressed trees, while using 2.3--10 times less space, and might be of interest in other scenarios.

The first passage time (FPT) problem is studied for superstatistical models assuming that the mesoscopic system dynamics is described by a Fokker-Planck equation. We show that all moments of the random intensive parameter associated to the superstatistical approach can be put in one-to-one correspondence with the moments of the FPT. For systems subjected to an additional uncorrelated external force, the same statistical information is obtained from the dependence of the FPT-moments on the external force. These results provide an alternative technique for checking the validity of superstatistical models. As an example, we characterize the mean FPT for a forced Brownian particle., Comment: 9 pages, 1 figure

Quantum correlations between two free spinless dissipative distinguishable particles (interacting with a thermal bath) are studied analytically using the quantum master equation and tools of quantum information. Bath-induced coherence and correlations in an infinite-dimensional Hilbert space are shown. We show that for temperature T > 0 the time-evolution of the reduced density matrix cannot be written as the direct product of two independent particles. We have found a time-scale that characterizes the time when the bath-induced coherence is maximum before being wiped out by dissipation (purity, relative entropy, spatial dispersion, and mirror correlations are studied). The Wigner function associated to the Wannier lattice (where the dissipative quantum walks move) is studied as an indirect measure of the induced correlations among particles. We have supported the quantum character of the correlations by analyzing the geometric quantum discord., Comment: 13 pages, 5 figures. arXiv admin note: substantial text overlap with arXiv:1512.08700

Quantum correlations and coherence generated between two free spinless particles in the lattice, interacting with a common quantum phonon bath, are studied. The reduced density matrix is solved using the Markov approach. We show that the bath induces correlations between the particles. The coherence induced by the bath is studied, calculating off-diagonal elements of the density matrix, spatiotemporal dispersion, purity and quantum mutual information. We find a characteristic time-scale pointing out when this coherence is maximum. In addition, a Wigner-like distribution in the phase-space (lattice) is introduced as an indirect indicator of the quantumness of total correlations and coherence induced by the thermal bath. The negative volume of the Wigner function also shows a behavior which is in agreement with the time-scale that we have found. A Gaussian distribution for the profile of particles is not obtained, and interference patterns are observed as the result of bath-induced coherence. As the temperature of the bath vanishes, the ballistic behavior of the tight-binding model is recovered. The geometric quantum discord is calculated, to characterize the nature of the correlations., Comment: 30 pages, 10 figures

We have investigated the time-evolution of a free particle in interaction with a phonon thermal bath, using the tight-binding approach. A dissipative quantum walk can be defined and many important non-equilibrium decoherence properties can be investigated analytically. The non-equilibrium statistics of a pure initial state have been studied. Our theoretical results indicate that the evolving wave-packet shows the suppression of Anderson's boundaries (ballistic peaks) by the presence of dissipation. Many important relaxation properties can be studied quantitatively, such as von Neumann's entropy and quantum purity. In addition, we have studied Wigner's function. The time-dependent behavior of the quantum entanglement between a free particle -in the lattice- and the phonon bath has been characterized analytically. This result strongly suggests the non-trivial time-dependence of the off-diagonal elements of the reduced density matrix of the system. We have established a connection between the quantum decoherence and the dissipative parameter arising from interaction with the phonon bath. The time-dependent behavior of quantum correlations has also been pointed out, showing continuous transition from quantum random walk to classical random walk, when dissipation increases., Comment: Submitted for publication. 17 pages, 6 figures

We introduce the quantum Levy walk to study transport and decoherence in a quantum random model. We have derived from second order perturbation theory the quantum master equation for a \textit{Levy-like particle}that moves along a lattice through hopping scale-free while interacting with a thermal bath of oscillators. The general evolution of the quantum Levy particle has been solved for different preparations of the system. We examine the evolution of the quantum purity, the localized correlation, and the probability to be in a lattice site, all them leading to important conclusions concerning quantum irreversibility and decoherence features. We prove that the quantum thermal mean-square displacement is finite under a constraint that is different when compared to the classical Weierstrass random walk. We prove that when the mean-square displacement is infinite the density of state has a complex null-set inside the Brillouin zone. We show the existence of a critical behavior in the continuous eigenenergy which is related to its non-differentiability and self-affine characteristics. In general our approach allows to study analytically quantum fluctuations and decoherence in a long-range hopping model., Comment: 26 pages, 6 figures