# On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance

Feijão P, Martinez F, Thévenin A (2015) *BMC Bioinformatics* 16(Suppl 19): S1.

Download

1471-2105-16-S19-S1.feijao.pdf
880.77 KB

*Journal Article*|

*Published*|

*English*

Author

Department

Abstract

Finding the smallest sequence of operations to transform one genome into another is an important problem in comparative genomics. The breakpoint graph is a discrete structure that has proven to be effective in solving distance problems, and the number of cycles in a cycle decomposition of this graph is one of the remarkable parameters to help in the solution of related problems. For a fixed k, the number of linear unichromosomal genomes (signed or unsigned) with n elements such that the induced breakpoint graphs have k disjoint cycles, known as the Hultman number, has been already determined. In this work we extend these results to multichromosomal genomes, providing formulas to compute the number of multichromosal genomes having a fixed number of cycles and/or paths. We obtain an explicit formula for circular multichromosomal genomes and recurrences for general multichromosomal genomes, and discuss how these series can be used to calculate the distribution and expected value of the rearrangement distance between random genomes.

Keywords

Publishing Year

ISSN

Financial disclosure

Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.

PUB-ID

### Cite this

Feijão P, Martinez F, Thévenin A. On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance.

*BMC Bioinformatics*. 2015;16(Suppl 19): S1.Feijão, P., Martinez, F., & Thévenin, A. (2015). On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance.

*BMC Bioinformatics*,*16*(Suppl 19), S1. doi:10.1186/1471-2105-16-s19-s1Feijão, P., Martinez, F., and Thévenin, A. (2015). On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance.

*BMC Bioinformatics*16:S1.Feijão, P., Martinez, F., & Thévenin, A., 2015. On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance.

*BMC Bioinformatics*, 16(Suppl 19): S1. P. Feijão, F. Martinez, and A. Thévenin, “On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance”,

*BMC Bioinformatics*, vol. 16, 2015, : S1. Feijão, P., Martinez, F., Thévenin, A.: On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance. BMC Bioinformatics. 16, : S1 (2015).

Feijão, Pedro, Martinez, Fábio, and Thévenin, Annelyse. “On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance”.

*BMC Bioinformatics*16.Suppl 19 (2015): S1.**Main File(s)**

File Name

1471-2105-16-S19-S1.feijao.pdf
880.77 KB

Access Level

Open Access

Last Uploaded

2016-02-24T12:44:08Z

This data publication is cited in the following publications:

This publication cites the following data publications:

### 1 Citation in Europe PMC

Data provided by Europe PubMed Central.

readat: An R package for reading and working with SomaLogic ADAT files.

Cotton RJ, Graumann J.,

PMID: 27146037

Cotton RJ, Graumann J.,

*BMC Bioinformatics*17(1), 2016PMID: 27146037

### 12 References

Data provided by Europe PubMed Central.

AUTHOR UNKNOWN, 2009

Genome rearrangements and sorting by reversals

AUTHOR UNKNOWN, 1996

AUTHOR UNKNOWN, 1996

On Hultman numbers

AUTHOR UNKNOWN, 2007

AUTHOR UNKNOWN, 2007

The distribution of cycles in breakpoint graphs of signed permutations

AUTHOR UNKNOWN, 2013

AUTHOR UNKNOWN, 2013

A unifying view of genome rearrangements

AUTHOR UNKNOWN, 2006

AUTHOR UNKNOWN, 2006

AUTHOR UNKNOWN, 1994

Finite, closed-form expressions for the partition function and for Euler, Bernoulli, and Stirling numbers

AUTHOR UNKNOWN, 0

AUTHOR UNKNOWN, 0

AUTHOR UNKNOWN, 2014

Efficient sorting of genomic permutations by translocation, inversion and block interchange.

Yancopoulos S, Attie O, Friedberg R.,

PMID: 15951307

Yancopoulos S, Attie O, Friedberg R.,

*Bioinformatics*21(16), 2005PMID: 15951307

A unifying view of genome rearrangements

AUTHOR UNKNOWN, 2006

AUTHOR UNKNOWN, 2006

Extending the algebraic formalism for genome rearrangements to include linear chromosomes.

Feijao P, Meidanis J.,

PMID: 24334378

Feijao P, Meidanis J.,

*IEEE/ACM Trans Comput Biol Bioinform*10(4), 2013PMID: 24334378

SNPtoGO: characterizing SNPs by enriched GO terms.

Schwarz DF, Hadicke O, Erdmann J, Ziegler A, Bayer D, Moller S.,

PMID: 18024970

Schwarz DF, Hadicke O, Erdmann J, Ziegler A, Bayer D, Moller S.,

*Bioinformatics*24(1), 2008PMID: 18024970

### Export

0 Marked Publications### Web of Science

View record in Web of Science®### Sources

PMID: 26695008

PubMed | Europe PMC