title: AN EFFICIENT ALGORITHM FOR CHINESE POSTMAN WALK ON BI-DIRECTED DE BRUIJN GRAPHS.
abstract: Sequence assembly from short reads is an important problem in biology. It is known that solving the sequence assembly problem exactly on a bi-directed de Bruijn graph or a string graph is intractable. However, finding a shortest double stranded DNA string (SDDNA) containing all thek-long words in the reads seems to be a good heuristic to get close to the original genome. This problem is equivalent to finding a cyclic Chinese Postman (CP) walk on the underlying unweighted bi-directed de Bruijn graph built from the reads. The Chinese Postman walk Problem (CPP) is solved by reducing it to a general bi-directed flow on this graph which runs inO(|E|2log2(|V|)) time. In this paper we show that the cyclic CPP on bi-directed graphs can be solved without reducing it to bi-directed flow. We present a Θ(p(|V| + |E|) log(|V|) + (dmaxp)3) time algorithm to solve the cyclic CPP on a weighted bi-directed de Bruijn graph, wherep= max{|{υ∣din(υ) -dout(υ) > 0}|, |{υ∣din(υ) -dout(υ) < 0}|} anddmax= max{∣din(υ) -dout(υ)}. Our algorithm performs asymptotically better than the bi-directed flow algorithm when the number ofimbalancednodespis much less than the nodes in the bi-directed graph. From our experimental results on various datasets, we have noticed that the value ofp/|V| lies between 0.08% and 0.13% with 95% probability. Many practical bi-directed de Bruijn graphs do not have cyclic CP walks. In such cases it is not clear how the bi-directed flow can be useful in identifying contigs. Our algorithm can handle such situations and identify maximal bi-directed sub-graphs that have CP walks. A Θ(p(|V| + |E|)) time heuristic algorithm based on these ideas has been implemented for the SDDNA problem. This algorithm was tested on short reads from a plant genome and achieves an approximation ratio of at most 1.0134. We also present a Θ((|V| + |E|) log(V)) time algorithm for the single source shortest path problem on bi-directed de Bruijn graphs, which may be of independent interest.
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut Storrs, CT 06269, USA.
authors.forename: Vamsi
authors.initials: V
authors.lastname: Kundeti
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut Storrs, CT 06269, USA.
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut Storrs, CT 06269, USA.
authors.forename: Heiu
authors.initials: H
authors.lastname: Dinh
keywords: Chinese Postman problem; Sequence assembly algorithms; bi-directed graphs; bioinformatics