干旱区生态环境知识资源中心(Arid): An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph

Arid

DOI	10.1145/3341731
	An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph
	Cairo, Massimo 1; Medvedev, Paul 2; Acosta, Nidia Obscura 3; Rizzi, Romeo 4; Tomescu, Alexandru, I 5
通讯作者	Cairo, Massimo
来源期刊	ACM TRANSACTIONS ON ALGORITHMS
ISSN	1549-6325
EISSN	1549-6333
出版年	2019
卷号	15 期号:4
英文摘要	In this article, we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Omega(nm). We implement this algorithm arid show that it is 9-12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).
英文关键词	Genome assembly safe and complete algorithm graph algorithm edge-covering walk strong bridge
类型	Article
语种	英语
国家	Italy ; USA ; Finland
开放获取类型	Green Published, Bronze
收录类别	SCI-E
WOS记录号	WOS:000496745500004
WOS关键词	SEQUENCE ; PERSISTENCY ; REGIONS
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS研究方向	Computer Science ; Mathematics
EI主题词	2019-10-01
资源类型	期刊论文
条目标识符	http://119.78.100.177/qdio/handle/2XILL650/310065
作者单位	1.Univ Trento, Dept Math, Via Sommarive 14, I-38123 Povo, Italy; 2.Penn State Univ, Dept Comp Sci & Engn, W316 Westgate Bldg, University Pk, PA 16802 USA; 3.Aalto Univ, Aalto SCI Comp Sci, Konemiehentie 2, Espoo 02150, Finland; 4.Univ Verona, Dept Comp Sci, CaVignal 2,Str Grazie 15, I-37134 Verona, Italy; 5.Univ Helsinki, Dept Comp Sci, POB 68, FI-00014 Helsinki, Finland
推荐引用方式 GB/T 7714	Cairo, Massimo,Medvedev, Paul,Acosta, Nidia Obscura,et al. An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph[J],2019,15(4).
APA	Cairo, Massimo,Medvedev, Paul,Acosta, Nidia Obscura,Rizzi, Romeo,&Tomescu, Alexandru, I.(2019).An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph.ACM TRANSACTIONS ON ALGORITHMS,15(4).
MLA	Cairo, Massimo,et al."An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph".ACM TRANSACTIONS ON ALGORITHMS 15.4(2019).