You are using an old browser with security vulnerabilities and can not use the features of this website.
Within the block seminar "Computational Models Inspired by Nature" organized by PD Dr. Henning Bordihn, Prof. Dr. Victor Mitrana of the University Bukarest will give two scientific talks. All those interested are cordially invited.
1. Talk: Thursday, 29.06.2017, 6:15 pm, Campus Griebnitzsee, building 4, room 0.02
A New Operation Suggested by DNA Biochemistry: Hairpin Completion
We propose a new formal operation on words and languages suggested by DNA manipulation, called hairpin completion. By this operation, that is based on the Watson-Crick complementarity, annealing and PCR, one can generate a set of words, starting from a single word.This operation is considered here as an abstract operation on formal languages. We settle the closure properties under the non-iterated version of this operation of some classes in the Chomsky hierarchy as well as some complexity classes.
Then we consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the completion of a language. We propose an O(nf(n)) time recognition algorithm for the hairpin completion of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages.
The iterated version of hairpin completion is then discussed. We propose an O(n2f(n)) time recognition algorithm for the iterated hairpin completion of a language recognizable in O(f(n)) time. The n2 factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.
2. Talk: Thursday, 06.07.2017, 8:15 am (!), Campus Griebnitzsee, building 4, room 0.02
Computing Translocation Distances
A basic problem in the area of combinatorial algorithms for genome evolution is to determine the minimum number of large scale evolutionary events (genome rearrangements) that transform a genome into another. 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 multichromosomal genomes and examine the complexity of computing this distance in the case of uniform translocation.
Our work differs from previous approaches in several respects: the strings representing chromosomes may have multiple occurrences of the same symbol, they may have common symbols, the number of copies of all strings in the initial set is assumed arbitrarily large. One exact algorithm and one approximation algorithms, both of them based on greedy strategies, are discussed. We present an exact polynomial algorithm when the target set is a singleton while a 2-approximation algorithm is provided when considering arbitrary target sets. Some open problems are finally formulated.