Kolloquiumsvortrag: Victor Mitrana, Universität Bukarest
16.05.2014 von 14:15 bis 16:00
LMS2 Ü2/K
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.