TY - Generic
T1 - Transforming men into mice (polynomial algorithm for genomic distance problem)
T2 - Foundations of Computer Science, Annual IEEE Symposium on
Y1 - 1995
A1 - Sridhar Hannenhalli
A1 - Pevzner, P. A.
KW - biology computing
KW - combinatorial properties
KW - comparative physical mapping data
KW - computable parameters
KW - duality (mathematics)
KW - duality theorem
KW - evolution (biological)
KW - Genetics
KW - genome rearrangement algorithm
KW - genomic distance problem
KW - genomic rearrangements
KW - human-mouse evolution
KW - mammalian evolution
KW - multi chromosomal genomes
KW - parsimonious rearrangement scenarios
KW - pattern matching
KW - polynomial algorithm
KW - polynomial time algorithm
KW - set theory
KW - sorting
KW - string matching
KW - strings
KW - zoo fish
AB - Many people believe that transformations of humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, J.H. Nadeau and B.A. Taylor (1984) estimated that surprisingly few genomic rearrangements (178/spl plusmn/39) happened since the divergence of human and mouse 80 million years ago. However, their analysis is nonconstructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131 reversals/translocaitons/fusions/fissions. A combination of the genome rearrangement algorithm with the recently proposed experimental technique called ZOO FISH suggests a new constructive approach to the 100 year old problem of reconstructing mammalian evolution.
JA - Foundations of Computer Science, Annual IEEE Symposium on
PB - IEEE Computer Society
CY - Los Alamitos, CA, USA
ER -