Genome Assemby, Chinese Postman, and Virtual Clusters

Channel:

Google TechTalks

Subscribers:

348,000

Published on October 9, 2007 3:48:00 AM ● Video Link: https://www.youtube.com/watch?v=-m7PFnSvmJM

Duration: 53:03

2,528 views

12

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...