Main Profile

At A Glance

Genome Assemby, Chinese Postman, and Virtual Clusters

Google Tech TalkMay 11, 2007ABSTRACTIn 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...
Length: 53:02

Contact

Questions about Genome Assemby, Chinese Postman, and Virtual Clusters

Want more info about Genome Assemby, Chinese Postman, and Virtual Clusters? Get free advice from education experts and Noodle community members.

  • Answer

Ask a New Question