*************************************************************************

                Department of Mathematical Sciences                       
                   The Johns Hopkins University                           
                                                                        
                              SEMINAR                                
                                                                        
*************************************************************************

Russell Schwartz                                  April 5, 2001
Informatics Research Group                        304 Whitehead Hall
Celera Genomics                                   Preseminar: 3:00 p.m.
                                                  Refreshments: 3:30 p.m.
                                                  Seminar: 4:00 p.m.

*************************************************************************

        HAPLOTYPE SEPARATION OF SHOTGUN ASSEMBLY FRAGMENTS

*************************************************************************

                             ABSTRACT

This talk will examine computational aspects of the problem of deducing
genetic haplotypes from genome sequence fragment data.  Fragment data is
generally produced from an organism's DNA by "shredding" it into small
pieces, which are individually sequenced and later reassembled as part
of a process called shotgun assembly.  In a higher organism, the
fragments will typically be made from two slightly different copies of
the genome due to the fact that the chromosomes that contain genetic
material come in pairs.  We are interested in locating from a pool of
fragments subsets each of whose members come from a single chromosome.
We call this problem haplotype separation.  This talk will define the
problem, present some formalizations, and examine the computational
complexity of the problem.  It will then describe a practical algorithm
developed for a specific formalization of the problem and discuss its
performance in practice.

*************************************************************************