Recent News
Computer Science undergraduate honored for cybersecurity research
February 20, 2025
Associate Professor Matt Lakin wins PECASE Award
January 31, 2025
Partnering for success: Computer Science students represent UNM in NASA and Supercomputing Competitions
December 11, 2024
New associate dean interested in helping students realize their potential
August 6, 2024
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 <[email protected]>
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.