Sage Journals: Discover world-class research

Abstract

We introduce a data structure, analysis, and visualization scheme called a cactus graph for comparing sets of related genomes. In common with multi-break point graphs and A-Bruijn graphs, cactus graphs can represent duplications and general genomic rearrangements, but additionally, they naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as two-dimensional multiple alignments and nets that can be visualized in circular genome plots. Supplementary Material is available at www.liebertonline.com/cmb.

Get full access to this article

View all access options for this article.

References

Alekseyev

, Pevzner

2008. Multi-break rearrangements and chromosomal evolution. Theoret. Comput Sci, 395:193–202.

Ben-Moshe

, Bhattacharya

2005. Efficient algorithms for the weighted 2-center problem in a cactus graph. Lect. Notes Comput. Sci., 3827:693–703.

Bergeron

, Mixtacki

, Stoye

2004. Reversal distance without hurdles and fortresses. Lect. Notes Comput. Sci., 3109:388–399.

Bergeron

, Stoye

2006. On the similarity of sets of permutations and its applications to genome comparison. J. Comput. Biol, 13:1340–1354.

Bignell

G.R.

, Santarius

, Pole

J.C.M.

et al. 2007. Architectures of somatic genomic rearrangement in human cancer amplicons at sequence-level resolution. Genome Res., 17:1296–1303.

Brudno

, Malde

, Poliakov

et al. 2003. Glocal alignment: finding rearrangements during alignment. Bioinformatics, 19,Suppl 1:i54–i62.

Caprara

1999. Formulations and hardness of multiple sorting by reversals. Proc. RECOMB 99, 84–93.

Carver

, Thomson

, Bleasby

et al. 2009. DNAplotter: circular and linear interactive genome visualization. Bioinformatics, 25:119–120.

Diskin

S.J.

, Hou

, Glessner

J.T.

et al. 2009. Copy number variation at 1q21.1 associated with neuroblastoma. Nature, 459:987–991.

10.

Durbin

, Eddy

, Krogh

et al. 1998. Biological Sequence Analysis. Cambridge University Press: New York.

11.

ENCODE-Consortium. 2007. Identification and analysis of functional elements in 1genome by the encode pilot project. Nature, 447:799–816.

12.

Hampton

O.A.

, Hollander

P.D.

, Miller

C.A.

et al. 2009. A sequence-level map of chromosomal breakpoints in the mcf-7 breast cancer cell line yields insights into the evolution of a cancer genome. Genome Res., 19:167–177.

13.

Hannenhalli

, Pevzner

P.A.

1995. Transforming men into mice (polynomial algorithm for genomic distance problem) Proc. 36th Annu. Symp. Found. Comput. Sci., 1:581–592.

14.

Hannenhalli

, Pevzner

P.A.

1999. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM, 46:1–27.

15.

Harary

, Uhlenbeck

1953. On the number of husimi trees, i. Proc. Nat. Acad. Sci. USA, 39:315–322.

16.

Higgins

D.G.

, Bleasby

A.J.

, Fuchs

1992. Clustal v: improved software for multiple sequence alignment. Comput. Appl. Biosci, 8:189–191.

17.

Kent

W.J.

, Baertsch

, Hinrichs

et al. 2003. Evolution's cauldron: duplication, deletion, and rearrangement in the mouse and human genomes. Proc. Natl. Acad. Sci. USA, 100:11484–11489.

18.

Korneyenko

N.M.

1994. Combinatorial algorithms on a class of graphs. Discrete Appl. Math., 54:215–217.

19.

Krzywinski

, Schein

, Birol

et al. 2009. Circos: an information aesthetic for comparative genomics. Genome Res., 19:1639–1645.

20.

Lee

, Grasso

, Sharlow

M.F.

2002. Multiple sequence alignment using partial order graphs. Bioinformatics, 18:452–464.

21.

Lunter

, Rocco

, Mimouni

et al. 2008. Uncertainty in homology inferences: assessing and improving genomic sequence alignment. Genome Res, 18:298–309.

22.

Pevzner

P.A.

, Pevzner

P.A.

, Tang

et al. 2004. De novo repeat classification and fragment assembly. Genome Res, 14:1786–1796.

23.

Raphael

, Zhi

, Tang

et al. 2004. A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Res, 14:2336–2346.

24.

Tannier

, Zheng

, Sankoff

2009. Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics, 10:120.

25.

Tetsuo

1991. On the number of solutions of a class of nonlinear resistive circuit. Proc. IEEE Int. Symp. Circuits Syst., 766–769.

26.

Tsin

Y.H.

2007. A simple 3-edge-connected component algorithm. Theory Comput. Syst., 40:125–142.

27.

Yancopoulos

, Attie

, Friedberg

2005. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics, 21:3340–3346.

28.

Zamazek

, Zerovnik

2005. Estimating the traffic on weighted cactus networks in linear time. Ninth Int. Conf. Inform. Visual, 536–541.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

32.01 MB

Cactus Graphs for Genome Comparisons

Abstract

Abstract

Get full access to this article

References

Supplementary Material