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

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2019-07-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-17
Series
ACM Transactions on Algorithms, Volume 15, issue 4
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 fasterin practice than the one of Tomescu and Medvedev (RECOMB 2016).
Description
Keywords
Other note
Citation
Cairo , M , Medvedev , P , Acosta , N O , Rizzi , R & Tomescu , A I 2019 , ' An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph ' , ACM Transactions on Algorithms , vol. 15 , no. 4 , 48 , pp. 1-17 . https://doi.org/10.1145/3341731