Distance Computation on Gene Order Data

December 9, 2004

Date: December 9, 2004
Time: 11:00 - 12:15 pm
Location: Woodward 149

Krister Swenson <kswenson@cs.unm.edu>
Department of Computer Science

The genome of an organism can be represented as a sequence of signed numbers. A natural question to investigate is how related two genomes are based on certain biologically plausible operations on their sequences. The canonical operation that has been considered is the inversion (or reversal) and the relative similarity between two genomes has been measured by finding the minimum numberof inversions that turn one sequence into another. Ten years ago Hannenhalli and Pevzner developed a rich theory and founda polynomial time algorithm to compute this distance for any two sequences, each with exactly one copy of a given number. Since then the theory has been refined and extended (to handle insertion/deletions) but there has existed no method to deal with two arbitrary sequences. In this presentation we investigate what operations are needed in orderto find a plausible distance between arbitrary sequences and show the techniques we are developing to handle them.