(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Complexity of Models for Sequence Assembly

Paul Medvedev
Department of Computer Science
University of Toronto

Tuesday, January 29, 2008, at 14:15
IMADA's Seminar Room

ABSTRACT

Graph-theoretic models have come to the forefront as some of the most powerful and practical methods for sequence assembly. Simultaneously, the computational hardness of the underlying graph algorithms has remained open. Here we present two theoretical results about the complexity of these models for sequence assembly. In the first part, we show sequence assembly to be NP-hard under two different models: string graphs and de Bruijn graphs. Together with an earlier result on the NP-hardness of overlap graphs, this demonstrates that all of the popular graph-theoretic sequence assembly paradigms are NP-hard.

In our second result, we give the first, to our knowledge, optimal polynomial time algorithm for genome assembly that explicitly models the double-strandedness of DNA. We solve the Chinese Postman Problem on bidirected graphs using bidirected flow techniques and show to how to use it to find the shortest double-stranded DNA sequence which contains a given set of $k$-long words. This algorithm has applications to sequencing by hybridization and short read assembly.

Host: Joan Boyar


SDU HOME | IMADA HOME | Previous Page
Last modified: Mon Jan 14 09:40:39 CET 2008
Joan Boyar (joan@imada.sdu.dk)

 


   Data protection at SDUDatabeskyttelse på SDU