[Colloquium] TTIC Talks: Paul Medvedev, UCSD

[Liv Leader]

When:     Friday, March 23 @ 11 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, Room #526

Who:       Paul Medvedev, UCSD

Title:      Algorithms for reconstructing genomes using high-throughput
sequencing

Abstract:

Whole-genome shotgun sequencing is an experimental technique used for
obtaining information about a genome's sequence, whereby it is broken up
into millions of short segments (called reads) whose sequence is then
determined. Recent technological advances hold the potential for tremendous
bio-medical discovery, enabling us to characterize the genomes of thousands
of species, to discover the wide spectrum of human genetic variation, and
to identify the wide range of bacteria making up the human microbiome.
However, the challenges posed by the novelty and sheer quantity of the data
are increasingly computational. A long-standing problem is how to infer the
genomic sequence of an unknown species from its reads, called genome
assembly. On the other hand, even within the same species the genomes of
two individuals differ, and the problem of detecting such variation has
received a lot of attention in the last few years.

In this talk, we will describe algorithms for assembling genomes,
discovering structural variants, and correcting errors in the reads. Our
methods are based on genome graphs, which capture the structure of a genome
even when its sequence is not fully known (as with the case of sequencing
data). We show how traditional genome graph models can be extended to
capture matepair information  (pairs of reads at a known distance apart),
which is crucial for improving the quality of assembly. We also show how
genome graphs can be used for detecting structural variation through a
method called CNVer.  CNVer is based on a maximum likelihood model, which
is optimized using a reduction to the bidirected network-flow problem. We
demonstrate CNVer's performance on a Yoruban human individual, showing a
high degree of accuracy and improvement over previous methods.

No prior knowledge of biology is required.

Host: Jinbo Xu, j3xu at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120320/9b2ec234/attachment.htm