A variant of the tandem duplication - random loss model of genome rearrangement

preprint2008arXivOpen access

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 αkα^k for α=1α=1 or α>=2α>=2 . In this paper, we study a variant of this model, where the cost of one step of width kk is 1 if k<=Kk <= K and ∞\infty if k>Kk > K, for any value of the parameter KinNK in N. We first show that permutations obtained after pp steps of width KK define classes of pattern-avoiding permutations. We also compute the numbers of duplication-loss steps of width KK necessary and sufficient to obtain any permutation of SnS_n, in the worst case and on average. In this second part, we may also consider the case K=K(n)K=K(n), a function of the size nn of the permutation on which the duplication-loss operations are performed.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.