Analysis of top-swap shuffling for genome rearrangements

• 成果类型: Article
• 署名作者: Bhatnagar, Nayantara; Caputo, Pietro; Tetali, Prasad; Vigoda, Eric
• 署名单位: University System of Georgia; Georgia Institute of Technology; Sapienza University Rome; University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051607000000177
• 发表日期: 2007
• 页码: 1424-1445
• 关键词: DISTRIBUTIONS; MODEL

摘要

We study Markov chains which model genome rearrangements. These models are useful for studying the equilibrium distribution of chromosomal lengths, and are used in methods for estimating genomic distances. The primary Markov chain studied in this paper is the top-swap Markov chain. The top-swap chain is a card-shuffling process with n cards divided over k decks, where the cards are ordered within each deck. A transition consists of choosing a random pair of cards, and if the cards lie in different decks, we cut each deck at the chosen card and exchange the tops of the two decks. We prove precise bounds on the relaxation time (inverse spectral gap) of the top-swap chain. In particular, we prove the relaxation time is Theta(n + k). This resolves an open question of Durrett.