Efficient Bubble Enumeration in Directed Graphs

Etienne Birmelé; Pierluigi Crescenzi; Rui Ferreira; Roberto Grossi; Vincent Lacroix; Andrea Marino; Nadia Pisanti; Gustavo Sacomoto; Marie-France Sagot

hal-00738927, version 1

Efficient Bubble Enumeration in Directed Graphs

Etienne Birmelé ¹, Pierluigi Crescenzi ², Rui Ferreira ³, Roberto Grossi ³, Vincent Lacroix^a^, 4, Andrea Marino ², Nadia Pisanti ³, Gustavo Sacomoto ⁴, Marie-France Sagot ( Auteur à contacter de préférence )^b^, 4

SPIRE (2012) 118-129

Résumé : Polymorphisms in DNA- or RNA-seq data lead to recognisable patterns in a de Bruijn graph representation of the reads obtained by sequencing. such patterns have been called mouths, or bubbles in the literature. They correspond to two vertex-disjoint directed paths between a source $s$ and a target $t$. Due to the high number of such bubbles that may be present in real data, their enumeration is a major issue concerning the efficiency of dedicated algorithms. We propose in this paper the first linear delay algorithm to enumerate all bubbles with a given source.

a – Université Claude Bernard - Lyon I
b – INRIA
1 : Université d'Evry-Val d'Essonne
Université d'Evry-Val d'Essonne
2 : Université de Florence
Università degli studi di Firenze
3 : Dipartimento di Informatica [Pisa] (DI)
University of Pisa
4 : BAMBOO (LBBE Lyon / INRIA Grenoble Rhône-Alpes)
Université Claude Bernard - Lyon I – INRIA – CNRS : UMR5558 – Laboratoire de Biométrie et Biologie Evolutive

hal-00738927, version 1
http://hal.inria.fr/hal-00738927
oai:hal.inria.fr:hal-00738927
Contributeur : Marie-France Sagot <>
Soumis le : Vendredi 5 Octobre 2012, 13:54:03
Dernière modification le : Mardi 11 Décembre 2012, 07:28:18

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1007/978-3-642-34109-0_13

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="hal-00738927"><analytic>
<author><persName><forename>Etienne</forename><surname>Birmelé</surname></persName>
<affiliation>
<orgName type="team">Université d'Evry-Val d'Essonne</orgName>
<country>FR</country>
<orgName type="institution">Université d'Evry-Val d'Essonne</orgName>
</affiliation>
</author>
<author><persName><forename>Pierluigi</forename><surname>Crescenzi</surname></persName>
<affiliation>
<orgName type="team">Université de Florence</orgName>
<country>IT</country>
<orgName type="institution">Università degli studi di Firenze</orgName>
</affiliation>
</author>
<author><persName><forename>Rui</forename><surname>Ferreira</surname></persName>
<affiliation>
<orgName type="laboratory">DI</orgName>
<orgName type="team">Dipartimento di Informatica [Pisa]</orgName>
<country>IT</country>
<orgName type="institution">University of Pisa</orgName>
</affiliation>
</author>
<author><persName><forename>Roberto</forename><surname>Grossi</surname></persName>
<affiliation>
<orgName type="laboratory">DI</orgName>
<orgName type="team">Dipartimento di Informatica [Pisa]</orgName>
<country>IT</country>
<orgName type="institution">University of Pisa</orgName>
</affiliation>
</author>
<author><persName><forename>Vincent</forename><surname>Lacroix</surname></persName>
<affiliation>
<orgName type="laboratory">LBBE Lyon / INRIA Grenoble Rhône-Alpes</orgName>
<orgName type="team">BAMBOO</orgName>
<country>FR</country>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5558</orgName>
<orgName type="institution">Laboratoire de Biométrie et Biologie Evolutive</orgName>
</affiliation>
</author>
<author><persName><forename>Andrea</forename><surname>Marino</surname></persName>
<affiliation>
<orgName type="team">Université de Florence</orgName>
<country>IT</country>
<orgName type="institution">Università degli studi di Firenze</orgName>
</affiliation>
</author>
<author><persName><forename>Nadia</forename><surname>Pisanti</surname></persName>
<affiliation>
<orgName type="laboratory">DI</orgName>
<orgName type="team">Dipartimento di Informatica [Pisa]</orgName>
<country>IT</country>
<orgName type="institution">University of Pisa</orgName>
</affiliation>
</author>
<author><persName><forename>Gustavo</forename><surname>Sacomoto</surname></persName>
<affiliation>
<orgName type="laboratory">LBBE Lyon / INRIA Grenoble Rhône-Alpes</orgName>
<orgName type="team">BAMBOO</orgName>
<country>FR</country>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5558</orgName>
<orgName type="institution">Laboratoire de Biométrie et Biologie Evolutive</orgName>
</affiliation>
</author>
<author><persName><forename>Marie-France</forename><surname>Sagot</surname></persName>
<affiliation>
<orgName type="laboratory">LBBE Lyon / INRIA Grenoble Rhône-Alpes</orgName>
<orgName type="team">BAMBOO</orgName>
<country>FR</country>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5558</orgName>
<orgName type="institution">Laboratoire de Biométrie et Biologie Evolutive</orgName>
</affiliation>
</author>
<title type="main" level="a">Efficient Bubble Enumeration in Directed Graphs</title></analytic><monogr><meeting>SPIRE</meeting><imprint><pubPlace><settlement>Cartagena</settlement><country>Colombie</country></pubPlace><biblScope type="publicationDate">2012-00-00</biblScope><biblScope type="pp">118-129</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-642-34109-0_13</idno><idno type="HALid">http://hal.inria.fr/hal-00738927</idno><idno type="HALFile">http://hal.inria.fr/hal-00738927/PDF/article15_spire.pdf</idno></biblStruct>
</listBibl>
</listBibl>