An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • BEC-INFM
  • Pennsylvania State University
  • University of Verona
  • University of Helsinki

Abstract

In this article, we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge.

In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Ω(nm). We implement this algorithm and show that it is 9--12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).

Details

Original languageEnglish
Article number48
Pages (from-to)1-17
JournalACM Transactions on Algorithms
Volume15
Issue number4
Publication statusPublished - 1 Jul 2019
MoE publication typeA1 Journal article-refereed

ID: 36076376