Abstract
In Soda'06, Chaudhuri, Chen, Mihaescu and Rao study algorithmic properties of the tandem duplication - random loss model of genome rearrangement, well-known in evolutionary biology. In their model, the cost of one step of duplication-loss of width k is for or . In this paper, we study a variant of this model, where the cost of one step of width is 1 if and if , for any value of the parameter . We first show that permutations obtained after steps of width define classes of pattern-avoiding permutations. We also compute the numbers of duplication-loss steps of width necessary and sufficient to obtain any permutation of , in the worst case and on average. In this second part, we may also consider the case , a function of the size of the permutation on which the duplication-loss operations are performed.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.