%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

        Sequence Assembly for High-Throughput Technologies

                     Steven Skiena

                Department of Computer Science
                State University of New York
                Stony Brook, NY 11794-4400 USA
                http://www.cs.sunysb.edu/~skiena


Next-generation sequencing technologies based on pyrosequencing and single
molecule methods are extremely promising, however the length and quality
of the resulting reads are radically different than those produced by
current sequencing machines.  We study the space of read length, sequencing
error rate, and coverage that lies well outside conventional assumptions
to determine the technological/economic parameters where de novo sequencing
will be achievable with these new technologies.  We demonstrate that genome
assembly on bacterial and human sequences is possible (a) with astonishingly
short reads, given sufficiently high coverage, and (b) under surprisingly
high error-rates, given long enough or plentiful enough reads.

(Joint work with J. Chen and A. Smirnov.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Biography: Steven Skiena is Professor of Computer Science at SUNY Stony Brook.
His research interests include the design of graph, string, and geometric
algorithms, and their applications (particularly to biology).  He is the
author of four books, including "The Algorithm Design Manual" and
"Calculated Bets: Computers, Gambling, and Mathematical Modeling to Win".
He is recipient of the ONR Young Investigator Award and the
IEEE Computer Science and Engineering Undergraduate Teaching Award.