6533b820fe1ef96bd1279202
RESEARCH PRODUCT
Whole mirror duplication-random loss model and pattern avoiding permutations
Jean-luc BarilRémi Vernaysubject
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]Class (set theory)0206 medical engineeringBinary number0102 computer and information sciences02 engineering and technology[ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]01 natural sciencesIdentity (music)Combinatorial problemsTheoretical Computer ScienceGray codeCombinatoricsPermutation[ INFO.INFO-BI ] Computer Science [cs]/Bioinformatics [q-bio.QM]Gene duplicationRandom loss[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Pattern avoiding permutationGenerating algorithmComputingMilieux_MISCELLANEOUSMathematicsDiscrete mathematicsWhole duplication-random loss modelMathematics::CombinatoricsGenomeParity of a permutationComputer Science Applications[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO][ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]Binary reflected Gray code010201 computation theory & mathematicsSignal Processing[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]020602 bioinformaticsAlgorithmsInformation Systemsdescription
International audience; In this paper we study the problem of the whole mirror duplication-random loss model in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this model after a given number p of duplications of the identity is the class of permutations avoiding the alternating permutations of length p2+1. We also compute the number of duplications necessary and sufficient to obtain any permutation of length n. We provide two efficient algorithms to reconstitute a possible scenario of whole mirror duplications from identity to any permutation of length n. One of them uses the well-known binary reflected Gray code (Gray, 1953). Other relative models are also considered.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-05-16 |