Kolloquiumsvortrag: Victor Mitrana
Kiel, Ludewig-Meyn-Str. 2, Übungsraum 2
Titel: "Computing translocation distances"
We consider two translocation operations suggested by the genome rearrangements. In this talk chromosomes are viewed as being linear strings that exchange each other prefixes in the translocation process. We define a distance between a pair of multi-chromosomal and examine the complexity of computing this distance in the case of uniform and non-uniform translocation. Two exact algorithms and two approximation algorithms, all of them based on greedy strategies, are discussed. Some open problems are finally formulated.