The chromosome inversion problem
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Various algorithms are considered which yield upper and lower bounds to the distance measure required but no algorithm giving the exact value has been found.
Abstract
We wish to calculate a measure of distance between two species for the purpose of constructing a phylogenetic tree. The data from which the distance measure is to be calculated is the order of the sequence of gene loci around a circular chromosome, and the distance between any two species is the minimum number of chromosomal inversions necessary to make the two sequences identical. There is no top or bottom to the chromosome so mirror image sequences are regarded as being identical. There is also no fixed 12 o'clock position. Various algorithms are considered which yield upper and lower bounds to the distance measure required but no algorithm giving the exact value has been found. A stochastic analog to this problem is also considered.