Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-Linear Chaining Extended

Kuosmanen, Anna; Paavilainen, Topi; Gagie, Travis; Chikhi, Rayan; Tomescu, Alexandru Ioan; Makinen, Veli

Type de document :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Titre :

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-Linear Chaining Extended

Auteur(s) :

Kuosmanen, Anna [Auteur]
Helsingin yliopisto = Helsingfors universitet = University of Helsinki
Paavilainen, Topi [Auteur]
Helsingin yliopisto = Helsingfors universitet = University of Helsinki
Gagie, Travis [Auteur]
Universidad Diego Portales [Santiago - Chili] [UDP]
Chikhi, Rayan [Auteur]

Bioinformatics and Sequence Analysis [BONSAI]
Tomescu, Alexandru Ioan [Auteur]
Helsingin yliopisto = Helsingfors universitet = University of Helsinki
Makinen, Veli [Auteur]
Helsinki Institute for Information Technology [HIIT]

Titre de la manifestation scientifique :

RECOMB 2018 - 22nd Annual International Conference on Research in Computational Molecular Biology

Ville :

Paris

Pays :

France

Date de début de la manifestation scientifique :

2018-04-21

Discipline(s) HAL :

Informatique [cs]/Bio-informatique [q-bio.QM]

Résumé en anglais : [en]

Aligning sequencing reads on graph representations of genomes is an important ingredient of pan-genomics. Such approaches typically find a set of local anchors that indicate plausible matches between substrings of a read ...
Lire la suite >Aligning sequencing reads on graph representations of genomes is an important ingredient of pan-genomics. Such approaches typically find a set of local anchors that indicate plausible matches between substrings of a read to subpaths of the graph. These anchor matches are then combined to form a (semi-local) alignment of the complete read on a subpath. Co-linear chaining is an algorithmically rigorous approach to combine the anchors. It is a well-known approach for the case of two sequences as inputs. Here we extend the approach so that one of the inputs can be a directed acyclic graph (DAGs), e.g. a splicing graph in transcriptomics or a variant graph in pan-genomics. This extension to DAGs turns out to have a tight connection to the minimum path cover problem, asking for a minimum-cardinality set of paths that cover all the nodes of a DAG. We study the case when the size $k$ of a minimum path cover is small, which is often the case in practice. First, we propose an algorithm for finding a minimum path cover of a DAG $(V,E)$ in $O(k|E|\log|V|)$ time, improving all known time-bounds when $k$ is small and the DAG is not too dense. Second, we introduce a general technique for extending dynamic programming (DP) algorithms from sequences to DAGs. This is enabled by our minimum path cover algorithm, and works by mimicking the DP algorithm for sequences on each path of the minimum path cover. This technique generally produces algorithms that are slower than their counterparts on sequences only by a factor $k$. Our technique can be applied, for example, to the classical longest increasing subsequence and longest common subsequence problems, extended to labeled DAGs. Finally, we apply this technique to the co-linear chaining problem. We also implemented the new co-linear chaining approach. Experiments on splicing graphs show that the new method is efficient also in practice.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :