Cactus graphs for genome comparisons

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce a data structure, analysis and visualization scheme called a cactus graph for comparing sets of related genomes. Cactus graphs capture some of the advantages of de Bruijn and breakpoint graphs in one unified framework. They naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as multiple alignments and nets that can be visualized in circular genome plots.

Original languageEnglish (US)
Title of host publicationResearch in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings
Pages410-425
Number of pages16
DOIs
StatePublished - Dec 23 2010
Event14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010 - Lisbon, Portugal
Duration: Apr 25 2010Apr 28 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6044 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010
CountryPortugal
CityLisbon
Period4/25/104/28/10

Fingerprint

Cactus
Genome
Genes
Graph in graph theory
Substructure
Data structures
Data Structures
Alignment
Visualization
Decompose

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Paten, B., Diekhans, M., Earl, D., John, J. S., Ma, J., Suh, B., & Haussler, D. (2010). Cactus graphs for genome comparisons. In Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings (pp. 410-425). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6044 LNBI). https://doi.org/10.1007/978-3-642-12683-3_27

Cactus graphs for genome comparisons. / Paten, Benedict; Diekhans, Mark; Earl, Dent; John, John St; Ma, Jian; Suh, Bernard; Haussler, David.

Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings. 2010. p. 410-425 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6044 LNBI).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Paten, B, Diekhans, M, Earl, D, John, JS, Ma, J, Suh, B & Haussler, D 2010, Cactus graphs for genome comparisons. in Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6044 LNBI, pp. 410-425, 14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010, Lisbon, Portugal, 4/25/10. https://doi.org/10.1007/978-3-642-12683-3_27
Paten B, Diekhans M, Earl D, John JS, Ma J, Suh B et al. Cactus graphs for genome comparisons. In Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings. 2010. p. 410-425. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-12683-3_27
Paten, Benedict ; Diekhans, Mark ; Earl, Dent ; John, John St ; Ma, Jian ; Suh, Bernard ; Haussler, David. / Cactus graphs for genome comparisons. Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings. 2010. pp. 410-425 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{1a82665cfb854b11aa021f2d02897139,
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. Cactus graphs capture some of the advantages of de Bruijn and breakpoint graphs in one unified framework. They naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as multiple alignments and nets that can be visualized in circular genome plots.",
author = "Benedict Paten and Mark Diekhans and Dent Earl and John, {John St} and Jian Ma and Bernard Suh and David Haussler",
year = "2010",
month = "12",
day = "23",
doi = "10.1007/978-3-642-12683-3_27",
language = "English (US)",
isbn = "3642126820",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "410--425",
booktitle = "Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings",

}

TY - GEN

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 - 2010/12/23

Y1 - 2010/12/23

N2 - We introduce a data structure, analysis and visualization scheme called a cactus graph for comparing sets of related genomes. Cactus graphs capture some of the advantages of de Bruijn and breakpoint graphs in one unified framework. They naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as multiple alignments and nets that can be visualized in circular genome plots.

AB - We introduce a data structure, analysis and visualization scheme called a cactus graph for comparing sets of related genomes. Cactus graphs capture some of the advantages of de Bruijn and breakpoint graphs in one unified framework. They naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as multiple alignments and nets that can be visualized in circular genome plots.

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

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

U2 - 10.1007/978-3-642-12683-3_27

DO - 10.1007/978-3-642-12683-3_27

M3 - Conference contribution

AN - SCOPUS:78650267295

SN - 3642126820

SN - 9783642126826

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 410

EP - 425

BT - Research in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings

ER -