The cycle graph introduced by Bafna and Pevzner is an important tool for evaluating the distance between two genomes, that is, the minimal number of rearrangements needed to transform one genome into another. We interpret this distance in topological terms and relate it to the random matrix theory. Namely, the number of genomes at a given 2-break distance from a fixed one (the Hultman number) is represented by a coefficient in the genus expansion of a matrix integral over the space of complex matrices with the Gaussian measure. We study generating functions for the Hultman numbers and prove that the two-break distance distribution is asymptotically normal.
Get full access to this article
View all access options for this article.
References
1.
AlekseyevM.2008. Multi-break rearrangements and breakpoint re-uses: from circular to linear genomes. J. Comp. Biol., 15, 1117–1131.
2.
AlexeevN., GoetzeF., and TikhomirovA.2010. Asymptotic distribution of singular values of powers of random matrices. Lithuanian Math. J., 50, 121–132.
3.
AndersenJ.E., PennerR.C., ReidysC.M., and WatermanM.S.2013. Topological classification and enumeration of RNA structures by genus. J. Math. Bio., 67, 1261–1278.
4.
BafnaV., and PevznerP.A.1998. Sorting by transpositions. SIAM Journal on Discrete Mathematics, 11, 224–240.
5.
BónaM., and FlynnR.2009. The average number of block interchanges needed to sort a permutation and a recent result of Stanley. Information Processing Letters, 109, 927–931.
6.
DoignonJ.-P., and LabarreA.2007. On Hultman numbers. Journal of Integer Sequences, 10, 1–13.
7.
HarerJ., and ZagierD.1986. The Euler characteristic of the moduli space of curves. Invent. Math., 85, 457–485.
8.
HultmanA.1999. Toric permutations [Master's thesis]. Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden.
9.
MulaseM.1998. Lectures on the asymptotic expansion of a Hermitian matrix integral. Supersymmetry and Integrable Models, 502, 91–134.
10.
ZvonkinA.1997. Matrix integrals and map enumeration: an accessible introduction. Math. Comput. Modeling, 26, 281–304.
