Linear-time superbubble identification algorithm for genome assembly

详细信息    查看全文

• 作者：Ljiljana Brankovic^a ; ^b ; ^{ljiljana.brankovic@newcastle.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Costas S. Iliopoulos^b ; ^{costas.iliopoulos@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Ritu Kundu^b ; ^{ritu.kundu@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Manal Mohamed^b ; ^{manal.mohamed@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Solon P. Pissis^b ; ^{solon.pissis@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Fatima Vayani^b ; ^{fatima.vayani@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Genome assembly ; de Bruijn graphs ; Superbubble
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P2
• 页码：374-383
• 全文大小：351 K

文摘

DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble  . In this paper, we propose an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515009147&_mathId=si1.gif&_user=111111111&_pii=S0304397515009147&_rdoc=1&_issn=03043975&md5=d7419cdf8d583cc23353fabcfba59f4c" title="Click to view the MathML source">O(n+m)class="mathContainer hidden">class="mathCode">$\mathcal{O}(n+m)$-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m   (directed) edges, improving the best-known class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515009147&_mathId=si2.gif&_user=111111111&_pii=S0304397515009147&_rdoc=1&_issn=03043975&md5=25ad98842bd69916f8718fb36e5bc853" title="Click to view the MathML source">O(mlog⁡m)class="mathContainer hidden">class="mathCode">$\mathcal{O}(m\log m)$-time algorithm by Sung et al.