----------------------------------------------------------------------
Speaker:	David Liben-Nowell
		MIT

Topic:		"Using Gossip To Compute The Distance Between Species"

Date:		Wednesday, 23 January 2002

Time:		11:00am - 12 noon

Venue:		Lecture Theater G
		(Chow Tak Sin Lecture Theater, near lift nos. 25/26)
		HKUST

ABSTRACT:

The "syntenic distance" is one of a number of recently-developed models
for computing the genetic difference between species.  It considers only
the assignment of genes to chromosomes (ignoring their relative order
within chromosomes), and models genetic mutations that affect that
assignment.  The syntenic distance is the minimum number of these
mutations necessary to transform one species into the other.  Computing
this distance is NP-hard.

In this talk, I will draw some tight technical connections between
syntenic distance and the "gossip problem" (or "telephone problem"), a
combinatorial puzzle well-studied in the 1970s.  I will use this
connection to give an exact value for the syntenic diameter - the maximum
syntenic distance between two species -- and describe a faster
exponential-time algorithm for syntenic distance.

The diameter result is joint work with Jon Kleinberg.




			For enquiries, please call 2358 7008
			  **** ALL are Welcome ****
---------------------------------------------------------------------------