Recent News
Inaugural School of Engineering Teaching Innovation Fellows selected
February 2, 2024
UNM computer scientist wins NSF CAREER Award to optimize supercomputer performance
February 1, 2024
Hand and Machine Lab’s Experimental Clay Exhibition closing celebration Nov. 17
November 15, 2023
Moses selected as special assistant to the dean for educational initiatives
October 3, 2023
News Archives
Distance Computation on Gene Order Data
December 9, 2004
Date: December 9, 2004Time: 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.