Cactus graphs for genome comparisons

Benedict Paten; Mark Diekhans; Dent Earl; John St John; Jian Ma; Bernard Suh; David Haussler

doi:10.1089/cmb.2010.0252

Cactus graphs for genome comparisons

Benedict Paten, Mark Diekhans, Dent Earl, John St John, Jian Ma, Bernard Suh, David Haussler

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	469-481
Number of pages	13
Journal	Journal of Computational Biology
Volume	18
Issue number	3
DOIs	https://doi.org/10.1089/cmb.2010.0252
State	Published - Mar 1 2011
Externally published	Yes

Keywords

Algorithms
cancer genomics
genomic rearrangements
sequence analysis

ASJC Scopus subject areas

Molecular Biology
Genetics
Computational Mathematics
Modeling and Simulation
Computational Theory and Mathematics

Online availability

10.1089/cmb.2010.0252

Library availability

Discover UIUC Full Text

Cite this

@article{10ba79f660f640faa63cc6f9801c1b78,

title = "Cactus graphs for genome comparisons",

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.",

keywords = "Algorithms, cancer genomics, genomic rearrangements, sequence analysis",

author = "Benedict Paten and Mark Diekhans and Dent Earl and John, {John St} and Jian Ma and Bernard Suh and David Haussler",

year = "2011",

month = mar,

day = "1",

doi = "10.1089/cmb.2010.0252",

language = "English (US)",

volume = "18",

pages = "469--481",

journal = "Journal of Computational Biology",

issn = "1066-5277",

publisher = "Mary Ann Liebert Inc.",

number = "3",

}

TY - JOUR

T1 - Cactus graphs for genome comparisons

AU - Paten, Benedict

AU - Diekhans, Mark

AU - Earl, Dent

AU - John, John St

AU - Ma, Jian

AU - Suh, Bernard

AU - Haussler, David

PY - 2011/3/1

Y1 - 2011/3/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - cancer genomics

KW - genomic rearrangements

KW - sequence analysis

UR - http://www.scopus.com/inward/record.url?scp=79952380591&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952380591&partnerID=8YFLogxK

U2 - 10.1089/cmb.2010.0252

DO - 10.1089/cmb.2010.0252

M3 - Article

C2 - 21385048

AN - SCOPUS:79952380591

SN - 1066-5277

VL - 18

SP - 469

EP - 481

JO - Journal of Computational Biology

JF - Journal of Computational Biology

IS - 3

ER -

Cactus graphs for genome comparisons

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this