Kolloquiumsvortrag: Victor Mitrana
16.05.2014 von 14:15 bis 15:30
Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2
Titel: Computing translocation distances
Abstract:
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.