{"entities":{"Q2003335":{"pageid":2014077,"ns":120,"title":"Item:Q2003335","lastrevid":56667333,"modified":"2026-03-18T14:23:07Z","type":"item","id":"Q2003335","labels":{"en":{"language":"en","value":"Direct superbubble detection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7077456"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$311F7CE0-31A1-469F-93BB-2615FA71C0AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"69a69085f2fdc7ff36a2dfe99f17019fdd5b519a","datavalue":{"value":{"text":"Direct superbubble detection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2003335$0073A69A-4315-4C7C-8CD7-3CC7DC676F3A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c413a9ae650833f09a892c374e6f593deb44d9e5","datavalue":{"value":"1461.68152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$F4A7DB2F-CE76-4C33-813C-8A3B39F44656","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"33cbaa9b6755df87e6bc39e95f68a49173790cf7","datavalue":{"value":{"entity-type":"item","numeric-id":1659719,"id":"Q1659719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$DD9DFB00-B007-439B-8FF9-0CD682A3AD46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a93e0417a54db04a001534bc4b28927ef06fcb34","datavalue":{"value":{"entity-type":"item","numeric-id":176199,"id":"Q176199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$E25E2ED9-E118-4055-9DFD-DF020127C722","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$6AA331F3-CDB3-4ADF-8186-3D4F5AE9AAF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95484946e883fc7b4dd3685da23c3ff319dc5c53","datavalue":{"value":{"time":"+2019-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2003335$44C7BC98-E474-4E97-93CA-703E7E388ABC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"233127aa9383ce1ab0f3bd6aeb68615cc098069d","datavalue":{"value":"Summary: Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. Linear-time algorithms for the enumeration superbubbles recently have become available. Current approaches require the decomposition of the input digraph into strongly-connected components, which are then analyzed separately. In principle, a single depth-first search could be used, provided one can guarantee that the root of the depth-first search (DFS)-tree is not itself located in the interior or the exit point of a superbubble. Here, we describe a linear-time algorithm to determine suitable roots for a DFS-forest that is guaranteed to identify the superbubbles in a digraph correctly. In addition to the advantages of a more straightforward implementation, we observe a nearly three-fold gain in performance on real-world datasets. We present a reference implementation of the new algorithm that accepts many commonly-used input formats for digraphs. It is available as open source from github.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003335$E4E2B672-E6F0-4BED-8C95-5FE953D92182","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$F23228E2-74F7-4BF3-B53E-4140A4F0322F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$14BA20A3-0515-4AED-BCA9-031C187D7DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$87D902DB-C11F-44F4-8DA1-CCA8DCEBF1B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$5A5A592F-4E53-4C0C-98F2-9B87E6070CF2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5cfa53e44f43598563ba5d102f1e93e336808ad7","datavalue":{"value":"7077456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$DFC58FDF-8A4E-4396-BD2B-7FD3CD11626A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2967bf5b1af5654c9e8bd58c7f48fed6894e8741","datavalue":{"value":"superbubble","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003335$7678CD9A-4ECB-434F-9479-E2209453856B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff7bf11626141f10491819543bc6e69eb57efdf3","datavalue":{"value":"depth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003335$A9B07E8E-C647-4AAE-9D44-8D907E612C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003335$29F3D74D-C825-4E0E-8005-7F32E9586D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003335$23326656-8656-46C7-9D9C-4A5C4795BEDC","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"804cb8a3eae947890eade4431aaed562b33122a2","datavalue":{"value":{"entity-type":"item","numeric-id":13371,"id":"Q13371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$089C948D-E778-41DE-A49C-CCE56DE37310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dfaab4e4b81d1d345c01e1ea50dfc6f386089d8e","datavalue":{"value":{"entity-type":"item","numeric-id":18424,"id":"Q18424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$16C47EFF-6F2B-43D5-BC8C-288784873D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b4014be2188da34f94073b77869226289bd56c5a","datavalue":{"value":{"entity-type":"item","numeric-id":16368,"id":"Q16368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$DFE17F22-5FE5-458B-AD58-364E04E9FB56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8bf42d0fd66acf369e3d5d44d7ebef6adc7ae452","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$3A47D3B9-FE7F-4A19-AA62-BEAE6C0FBB35","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$16C2C775-7187-4C91-92AD-F75CF19A3E1C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ab4ee31ba8268f62c5cc22d7b20bdf8e637c1f8","datavalue":{"value":"https://doi.org/10.3390/a12040081","type":"string"},"datatype":"url"},"type":"statement","id":"Q2003335$5CA0CE8C-FEED-4B78-ACDE-AC2CF624DA79","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8411c91f9c00ab5baa642b76f4bba13951157cf5","datavalue":{"value":"W2937634726","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$B12DF754-47EE-449F-BA09-14C8F97D0142","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36668365b781aef3815bad53aed4aa2e26c1fade","datavalue":{"value":{"entity-type":"item","numeric-id":1706509,"id":"Q1706509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$50031FD5-203B-4CB3-8196-3066C1289A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbf345286dc9af79f0afaa2c43dbe3291d4107c7","datavalue":{"value":{"entity-type":"item","numeric-id":897907,"id":"Q897907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$6E19905C-FDB9-4075-8C19-3A3F99949440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$C45BC600-8022-423A-909B-9B33B65CC811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d920cb0768d10cdb8dd1451149569674134bfb","datavalue":{"value":{"entity-type":"item","numeric-id":5915788,"id":"Q5915788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$B3058F8F-483F-4FD6-9AE5-E69696ED3046","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3ef1abdd02976510f645e52c2f9a6cb6174e40b7","datavalue":{"value":"Q128038794","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$920C8F57-1966-4E46-9D41-6BF2D6F7DB98","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b23ad95db72c82dd66911012c9c5a825865b90ca","datavalue":{"value":"10.3390/A12040081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003335$8A9A7983-781F-4E62-8CC6-9D3D4C119F92","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99f005b8a81dbfbd36b6f96e7d08bdc66df50164","datavalue":{"value":{"entity-type":"item","numeric-id":2405421,"id":"Q2405421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"877cb043e3d825b208c7c070e39cd4e92745a289","datavalue":{"value":{"amount":"+0.76223797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2003335$8CAA46BF-B2FE-4345-B4C1-62CBD1A5B38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbd6d45b4fd82e464d92b5441a870e0c79a41cf8","datavalue":{"value":{"entity-type":"item","numeric-id":4603731,"id":"Q4603731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3bc8bf726a61697c48ca45c9a6763025d13baeb","datavalue":{"value":{"amount":"+0.76139903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2003335$BFC41202-D276-4CB6-B443-884F717B0C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94f8cecbe2293fe3185a9c170623105b5c8506b1","datavalue":{"value":{"entity-type":"item","numeric-id":3057962,"id":"Q3057962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c646b922e12546beb169d544f169a24cca5d879","datavalue":{"value":{"amount":"+0.75453305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2003335$DC5148C3-2207-4823-92F9-77314E5414CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d874926f8cfd7782fdfcb3ca876a46ebf74c49e","datavalue":{"value":{"entity-type":"item","numeric-id":1949904,"id":"Q1949904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1615d7ae7c9fa437d2fdc86ad00e3aec0ddc28a8","datavalue":{"value":{"amount":"+0.73917514","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2003335$B7E4E9C3-7D23-4ECF-B9F4-5CCEAAE3379C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d32601def01d8a54aba1f1e7e95dabe47c108137","datavalue":{"value":{"entity-type":"item","numeric-id":4531734,"id":"Q4531734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3461359370584a2df6cfede10fbce3f9839ee1ae","datavalue":{"value":{"amount":"+0.73885113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2003335$CEE4C25F-983F-4D0C-88EE-0F79EA226A42","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003335$EF68301D-4F46-4792-8B47-7A687E9EB4AD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2003335","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2003335"}}}}}