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

作     者：Bouvel, Mathilde Rossin, Dominique 

作者机构：Univ Paris Diderot LIAFA CNRS F-75205 Paris 13 France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2009年第410卷第8-10期

页      面：847-858页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Sorting Permutations Pattern Genome rearrangement Tandem duplication - random loss model Pattern-avoiding permutations 

摘      要：In [K. Chaudhuri, K. Chen, R. Mihaescu, S. Rao, On the tandem duplication-random loss model of genome rearrangement, in: SODA, 2006, pp. 564-570]. 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 alpha(k) for alpha = 1 or alpha = 2. In this paper, we study a variant of this model, where the cost of one step of width k is 1 if k K, for any value of the parameter K is an element of N boolean OR {infinity}. We first show that permutations obtained after p steps of width K define classes of pattern-avoiding permutations. We also compute the numbers Of duplication-loss steps of width K necessary and sufficient to obtain any permutation of S(n) in the worst case and on average. In this second part, we may also consider the case K = K(n), a function of the size n of the permutation oil which the duplication-loss operations are performed. (C) 2008 Elsevier B.V. All rights reserved.