3 citations · 3 across the 8 of their papers we have counts for
11 papers
Computing Ultrabubbles in Linear Time by Reduction to Weak Superbubbles in the Double Covering Graph
Sebastian Schmidt, Juha Harviainen, Corentin Moumard +3
In recent years, in attempts to capture variation structures in genomic and pangenomic graphs, the zoo of bubbles has been filled with more and more different variants. The first m…
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…
Improving Decision Trees through the Lens of Parameterized Local Search
Juha Harviainen, Frank Sommer, Manuel Sorge
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut.…
Graph Reconstruction with a Connected Components Oracle
Juha Harviainen, Pekka Parviainen
In the Graph Reconstruction (GR) problem, the goal is to recover a hidden graph by utilizing some oracle that provides limited access to the structure of the graph. The interest is…
Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Juha Harviainen, Frank Sommer, Manuel Sorge +1
We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decisi…
Quantum Speedups for Bayesian Network Structure Learning
Juha Harviainen, Kseniya Rychkova, Mikko Koivisto
The Bayesian network structure learning (BNSL) problem asks for a directed acyclic graph that maximizes a given score function. For networks with nodes, the fastest known algor…
Approximating the Permanent with Deep Rejection Sampling
Juha Harviainen, Antti Röyskö, Mikko Koivisto
We present a randomized approximation scheme for the permanent of a matrix with nonnegative entries. Our scheme extends a recursive rejection sampling method of Huber and Law (SODA…