{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:52:51Z","timestamp":1763535171153},"reference-count":5,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>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 the k-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 in O(|E|<jats:sup>2<\/jats:sup>log<jats:sup>2<\/jats:sup>(|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 \u0398(p(|V| + |E|) log (|V|) + (d<jats:sub>max<\/jats:sub>p)<jats:sup>3<\/jats:sup>) time algorithm to solve the cyclic CPP on a weighted bi-directed de Bruijn graph, where p = max {|{v|d<jats:sub>in<\/jats:sub>(v) - d<jats:sub>out<\/jats:sub>(v) &gt; 0}|, |{v|d<jats:sub>in<\/jats:sub>(v) - d<jats:sub>out<\/jats:sub>(v) &lt; 0}|} and d<jats:sub>max<\/jats:sub>= max {|d<jats:sub>in<\/jats:sub>(v) - d<jats:sub>out<\/jats:sub>(v)}. Our algorithm performs asymptotically better than the bi-directed flow algorithm when the number of imbalanced nodes p is much less than the nodes in the bi-directed graph. From our experimental results on various datasets, we have noticed that the value of p\/|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 \u0398(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 \u0398((|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.<\/jats:p>","DOI":"10.1142\/s179383091250019x","type":"journal-article","created":{"date-parts":[[2012,6,19]],"date-time":"2012-06-19T14:55:53Z","timestamp":1340117753000},"page":"1250019","source":"Crossref","is-referenced-by-count":3,"title":["AN EFFICIENT ALGORITHM FOR CHINESE POSTMAN WALK ON BI-DIRECTED DE BRUIJN GRAPHS"],"prefix":"10.1142","volume":"04","author":[{"given":"VAMSI","family":"KUNDETI","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SANGUTHEVAR","family":"RAJASEKARAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HEIU","family":"DINH","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,6,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1038\/35057062"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1058040"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1101\/gr.074492.107"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.171285098"},{"key":"rf5","doi-asserted-by":"crossref","first-page":"ii79","DOI":"10.1093\/bioinformatics\/bti1114","volume":"21","author":"Myers E. W.","journal-title":"Bioinformatics"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091250019X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T20:52:51Z","timestamp":1714078371000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091250019X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":5,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,6,21]]},"published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1142\/S179383091250019X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091250019x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}