{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:24Z","timestamp":1740109284765,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T00:00:00Z","timestamp":1567209600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T00:00:00Z","timestamp":1567209600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00453-019-00619-z","type":"journal-article","created":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T09:30:35Z","timestamp":1567243835000},"page":"898-914","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Bubble Generators in Directed Graphs"],"prefix":"10.1007","volume":"82","author":[{"given":"V.","family":"Acu\u00f1a","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G. F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Lima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Sacomoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.-F.","family":"Sagot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9797-7592","authenticated-orcid":false,"given":"B.","family":"Sinaimeri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,31]]},"reference":[{"key":"619_CR1","doi-asserted-by":"crossref","unstructured":"Acu\u00f1a, V., Grossi, R., Italiano, G.F., Lima, L., Rizzi, R., Sacomoto, G., Sagot, M., Sinaimeri, B.: On bubble generators in directed graphs. In: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, Eindhoven, The Netherlands, June 21\u201323 Lecture Notes in Computer Science, vol. 10520, pp. 18\u201331. Springer (2017)","DOI":"10.1007\/978-3-319-68705-6_2"},{"issue":"1","key":"619_CR2","doi-asserted-by":"publisher","first-page":"4307","DOI":"10.1038\/s41598-018-21770-7","volume":"8","author":"C Benoit-Pilven","year":"2018","unstructured":"Benoit-Pilven, C., Marchet, C., Chautard, E., Lima, L., Lambert, M.P., Sacomoto, G., Rey, A., Cologne, A., Terrone, S., Dulaurier, L., Claude, J.B., Bourgeois, C., Auboeuf, D., Lacroix, V.: Complementarity of assembly-first and mapping-first approaches for alternative splicing annotation and differential analysis from RNAseq data. Sci. Rep. 8(1), 4307 (2018)","journal-title":"Sci. Rep."},{"key":"619_CR3","doi-asserted-by":"crossref","unstructured":"Birmel\u00e9, E., Crescenzi, P., Ferreira, R., Grossi, R., Lacroix, V., Marino, A., Pisanti, N., Sacomoto, G., Sagot, M.F.: Efficient bubble enumeration in directed graphs. In: SPIRE, pp. 118\u2013129 (2012)","DOI":"10.1007\/978-3-642-34109-0_13"},{"key":"619_CR4","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Graduate Texts in Mathematics, vol. 184. Springer, Berlin (1998)"},{"key":"619_CR5","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.tcs.2015.10.021","volume":"609","author":"L Brankovic","year":"2016","unstructured":"Brankovic, L., Iliopoulos, C.S., Kundu, R., Mohamed, M., Pissis, S.P., Vayani, F.: Linear-time superbubble identification algorithm for genome assembly. Theor. Comput. Sci. 609, 374\u2013383 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"619_CR6","series-title":"The MIT Electrical Engineering and Computer Science Series","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"1991","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Electrical Engineering and Computer Science Series. MIT Press, Cambridge (1991)"},{"key":"619_CR7","series-title":"Prentice-Hall Series in Automatic Computation","volume-title":"Graph Theory with Applications to Engineering and Computer Science","author":"N Deo","year":"1974","unstructured":"Deo, N.: Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Englewood Cliffs (1974)"},{"issue":"1","key":"619_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1093\/bioinformatics\/bts635","volume":"29","author":"A Dobin","year":"2013","unstructured":"Dobin, A., Davis, C.A., Schlesinger, F., Drenkow, J., Zaleski, C., Jha, S., Batut, P., Chaisson, M., Gingeras, T.R.: Star: ultrafast universal rna-seq aligner. Bioinformatics 29(1), 15\u201321 (2013)","journal-title":"Bioinformatics"},{"issue":"2","key":"619_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7151\/dmgt.1200","volume":"23","author":"PM Gleiss","year":"2003","unstructured":"Gleiss, P.M., Leydold, J., Stadler, P.F.: Circuit bases of strongly connected digraphs. Discuss. Math. Gr. Theory 23(2), 241\u2013260 (2003)","journal-title":"Discuss. Math. Gr. Theory"},{"issue":"2","key":"619_CR10","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z Iqbal","year":"2012","unstructured":"Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., McVean, G.: De novo assembly and genotyping of variants using colored de bruijn graphs. Nat. Genet. 44(2), 226\u2013232 (2012)","journal-title":"Nat. Genet."},{"issue":"4","key":"619_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.cosrev.2009.08.001","volume":"3","author":"T Kavitha","year":"2009","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., Zweig, K.A.: Cycle bases in graphs characterization, algorithms, complexity, and applications. Comput. Sci. Rev. 3(4), 199\u2013243 (2009). https:\/\/doi.org\/10.1016\/j.cosrev.2009.08.001","journal-title":"Comput. Sci. Rev."},{"issue":"4","key":"619_CR12","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00224-006-1319-6","volume":"40","author":"T Kavitha","year":"2007","unstructured":"Kavitha, T., Mehlhorn, K.: Algorithms to compute minimum cycle bases in directed graphs. Theory Comput. Syst. 40(4), 485\u2013505 (2007)","journal-title":"Theory Comput. Syst."},{"key":"619_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/s13015-017-0091-2","volume":"12","author":"L Lima","year":"2017","unstructured":"Lima, L., Sinaimeri, B., Sacomoto, G., Lopez-Maestre, H., Marchet, C., Miele, V., Sagot, M.F., Lacroix, V.: Playing hide and seek with repeats in local and global de novo transcriptome assembly of short RNA-seq reads. Algorithms Mol. Biol. 12, 2\u20132 (2017). https:\/\/doi.org\/10.1186\/s13015-017-0091-2","journal-title":"Algorithms Mol. Biol."},{"key":"619_CR14","doi-asserted-by":"crossref","first-page":"22","DOI":"10.4064\/fm-28-1-22-32","volume":"28","author":"S MacLane","year":"1937","unstructured":"MacLane, S.: A combinatorial condition for planar graphs. Fundamenta Mathematicae 28, 22\u201332 (1937)","journal-title":"Fundamenta Mathematicae"},{"issue":"6","key":"619_CR15","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ygeno.2010.03.001","volume":"95","author":"JR Miller","year":"2010","unstructured":"Miller, J.R., Koren, S., Sutton, G.: Assembly algorithms for next-generation sequencing data. Genomics 95(6), 315\u2013327 (2010)","journal-title":"Genomics"},{"key":"619_CR16","first-page":"338","volume-title":"Lecture Notes in Computer Science","author":"Taku Onodera","year":"2013","unstructured":"Onodera, T., Sadakane, K., Shibuya, T.: Detecting superbubbles in assembly graphs. In: Algorithms in Bioinformatics, Lecture Notes in Computer Science, vol. 8126, pp. 338\u2013348. Springer, Berlin (2013)"},{"issue":"9","key":"619_CR17","doi-asserted-by":"publisher","first-page":"1786","DOI":"10.1101\/gr.2395204","volume":"14","author":"PA Pevzner","year":"2004","unstructured":"Pevzner, P.A., Tang, H., Tesler, G.: De novo repeat classification and fragment assembly. Genome Res. 14(9), 1786\u20131796 (2004)","journal-title":"Genome Res."},{"issue":"S\u20136","key":"619_CR18","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1186\/1471-2105-13-S6-S5","volume":"13","author":"G Sacomoto","year":"2012","unstructured":"Sacomoto, G., Kielbassa, J., Chikhi, R., Uricaru, R., Antoniou, P., Sagot, M.F., Peterlongo, P., Lacroix, V.: Kissplice: de-novo calling alternative splicing events from rna-seq data. BMC Bioinf. 13(S\u20136), S5 (2012)","journal-title":"BMC Bioinf."},{"key":"619_CR19","first-page":"99","volume-title":"Lecture Notes in Computer Science","author":"Gustavo Sacomoto","year":"2013","unstructured":"Sacomoto, G., Lacroix, V., Sagot, M.F.: A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs and its application to the detection of alternative splicing in RNA-seq data. In: WABI, pp. 99\u2013111 (2013)"},{"issue":"8","key":"619_CR20","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1089\/cmb.2009.0108","volume":"16","author":"M Sammeth","year":"2009","unstructured":"Sammeth, M.: Complete alternative splicing events are bubbles in splicing graphs. J. Comput. Biol. 16(8), 1117\u20131140 (2009)","journal-title":"J. Comput. Biol."},{"key":"619_CR21","volume-title":"Linear Algebra","author":"GE Shilov","year":"1977","unstructured":"Shilov, G.E.: Linear Algebra. Dover Publications, New York (1977). (Trans. R. A. Silverman)"},{"issue":"6","key":"619_CR22","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"JT Simpson","year":"2009","unstructured":"Simpson, J.T., Wong, K., Jackman, S.D., Schein, J.E., Jones, S.J.M., Birol, I.: ABySS: A parallel assembler for short read sequence data. Genome Res. 19(6), 1117\u20131123 (2009)","journal-title":"Genome Res."},{"issue":"4","key":"619_CR23","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1109\/TCBB.2014.2385696","volume":"12","author":"WK Sung","year":"2015","unstructured":"Sung, W.K., Sadakane, K., Shibuya, T., Belorkar, A., Pyrogova, I.: An $$O(m \\log m)$$-time algorithm for detecting superbubbles. IEEE\/ACM Trans. Comput. Biol. Bioinf. 12(4), 770\u2013777 (2015)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"2","key":"619_CR24","doi-asserted-by":"publisher","first-page":"e11","DOI":"10.1093\/nar\/gku1187","volume":"43","author":"R Uricaru","year":"2015","unstructured":"Uricaru, R., Rizk, G., Lacroix, V., Quillery, E., Plantard, O., Chikhi, R., Lemaitre, C., Peterlongo, P.: Reference-free detection of isolated SNPs. Nucl. Acids Res. 43(2), e11 (2015)","journal-title":"Nucl. Acids Res."},{"issue":"5","key":"619_CR25","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1093\/bioinformatics\/btu706","volume":"31","author":"R Younsi","year":"2015","unstructured":"Younsi, R., MacLean, D.: Using $$2k+2$$ bubble searches to find single nucleotide polymorphisms in k-mer graphs. Bioinformatics 31(5), 642\u2013646 (2015)","journal-title":"Bioinformatics"},{"key":"619_CR26","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"D Zerbino","year":"2008","unstructured":"Zerbino, D., Birney, E.: Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Res. 18, 821\u2013829 (2008)","journal-title":"Genome Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00619-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00619-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00619-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T01:53:33Z","timestamp":1664243613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00619-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,31]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["619"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00619-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,8,31]]},"assertion":[{"value":"1 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}