Genome Assemby, Chinese Postman, and Virtual Clusters
2,555 views · Published 9 October 2007 · 53:03 · Indexed 5 October 2026
Channel: Google TechTalks · 2007 · Howto & Style
Google Tech Talk May 11, 2007 ABSTRACT In the first half of the talk I will discuss several algorithmic results affecting whole genome assembly -- the problem of assembling a genome from short pieces (called reads). This problem is often reduced to various path problems on graphs. We will first show that the problem of finding the Shortest Chinese Superwalk on a de Bruijn graph is NP-complete/hard, hence demonstrating the computational equivalence of two methods for sequenceassembly: the String Graph approach of Myers et al and the Eulerian Superpath approach of Pevzner et al. We will also demonstrate a simple polynomial time algorithm separating complimentary paths on a graph, which is...
More from this channel
-
34:17
Thinglink - A Free Product Code for Creative Work
-
32:48
Thinking Beyond Borders
-
44:29
Understanding Urban Environments Through the Use of...
-
46:04
Customizable Scalable Compute Intensive Stream Queries
-
51:26
All The Government's Information
-
41:35
Combining Discriminative Features to Infer Complex...
-
59:42
Dimensions of Reputation in Electronic Markets
-
46:50
Accessing Legacy Documents in the iPod Age