Manuel Cáceres

Manuel Cáceres

Doctoral Student

University of Helsinki

Biography

I am a Doctoral Student from University of Helsinki. I work under the supervision of Alexandru I. Tomescu in the Graph Algorithms team, part of the Algorithmic Bioinformatics group at the Department of Computer Science. My Doctoral Thesis is titled “Parameterized and Safe & Complete Graph Algorithms for Bioinformatics”.

Previously, I was a Master Student from the Department of Computer Science at University of Chile. I worked under the supervision of Gonzalo Navarro. My thesis is titled “Compressed Suffix Trees for Repetitive Collections based on Block Trees”.

Interests

  • Algorithmic Bioinformatics
  • Graph Algorithms
  • String Algorithms
  • Compressed Data Structures
  • Safe & Complete Algorithms
  • Parameterized Algorithms

Education

  • PhD. in Computer Science, 2023

    University of Helsinki

  • MSc. in Computer Science, 2019

    University of Chile

  • Computer Science Engineering, Minor in Algorithms and Combinatorial Optimization, 2019

    University of Chile

  • BSc. in Computer Science, 2016

    University of Chile

Recent Publications

Sorting Finite Automata via Partition Refinement

We provide a $O(|\delta| \log |Q|)$-time algorithm computing a co-lex total preorder when the input is a Wheeler NFA, and an algorithm with the same time complexity computing the smallest-width co-lex partial order of any DFA.

Minimum Path Cover: The Power of Parameterization

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.

Minimum Chain Cover in Almost Linear Time

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. We present an algorithm running in time $O(T_{MF}(|E|) + (|V|+|E|)\log{k})$.

Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond

We present the first parameterized algorithms for SMLG in DAGs, derived from a generalization of the Knuth-Morris-Pratt algorithm optimized to work in time proportional to the number of prefix-incomparable matches. We obtain parameterizations in the topological structure of $G$, by studying a special class of DAGs called funnels and generalizing them to $k$-funnels and the class $ST_k$.

Chaining of Maximal Exact Matches in Graphs

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$.