10 papers
The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles
Sebastian Schmidt, Juha Harviainen, Corentin Moumard +3
Bidirected graphs are a common generalisation of directed graphs where arcs can also be incoming to both their incident nodes, or outgoing from both their incident nodes. Such arcs…
Exact and Approximate Algorithms for Polytree Learning
Juha Harviainen, Frank Sommer, Manuel Sorge
Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of variables as a directed forest and are motivated by their more…
Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
Francisco Sena, Aleksandr Politov, Corentin Moumard +6
A fundamental algorithmic problem in computational biology is to find all subgraphs of a given type (superbubbles, snarls, and ultrabubbles) in a directed or bidirected input graph…
Learning Bayesian and Markov Networks with an Unreliable Oracle
Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma
We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded…
Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework
Francisco Sena, Aleksandr Politov, Corentin Moumard +4
Snarls and superbubbles are fundamental pangenome decompositions capturing variant sites. These bubble-like structures underpin key tasks in computational pangenomics, including st…
Scaling Up Bayesian DAG Sampling
Daniele Nikzad, Alexander Zhilkin, Juha Harviainen +3
Bayesian inference of Bayesian network structures is often performed by sampling directed acyclic graphs along an appropriately constructed Markov chain. We present two techniques…