Expected number of inversions after a sequence of random adjacent transpositions

Simple item page
dc.creatorEriksson, Henrik
dc.creatorEriksson, Kimmo
dc.creatorSjostrand, Jonas
dc.date2004-11-09
dc.date.accessioned2026-07-07T05:14:07Z
dc.date.available2026-07-07T05:14:07Z
dc.descriptionIn the evolution of a genome, the gene sequence is sometimes rearranged, for example by transposition of two adjacent gene blocks. In biocombinatorics, one tries to reconstruct these rearrangement incidents from the resulting permutation. It seems that the algorithms used are too effective and find a shorter path than the real one. For the simplified case of adjacent transpositions, we give expressions for the expected number of inversions after t random moves. This average can be much smaller than t, a fact that has largely been neglected so far.
dc.description10 pages, presented at FPSAC 2000
dc.identifierhttps://arxiv.org/abs/math/0411197
dc.identifierhttp://arxiv.org/abs/math/0411197
dc.identifierSpringer Lecture Notes special volume for FPSAC 2000, pages 677-685
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/73159
dc.subjectCombinatorics
dc.subjectGenomics
dc.subject92D15, 60C05; 05E15
dc.titleExpected number of inversions after a sequence of random adjacent transpositions
dc.typetext

Files

Collections

arXiv