Syntenic Layout of Two Assemblies of Related Genomes

Olaf Delgado Friedrichs; Aaron L. Halpern; Ross Lippert; Christian Rausch; Stephan C. Schuster; Daniel H. Huson

Syntenic Layout of Two Assemblies of Related Genomes

Olaf Delgado Friedrichs, Aaron L. Halpern, Ross Lippert, Christian Rausch, Stephan C. Schuster, Daniel H. Huson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

To facilitate research in comparative genomics, sequencing projects are increasingly aimed at assembling the genomes of closely related organisms. Given two incomplete assemblies of two related genomes, the question arises how to use the similarity of the two sequences to obtain a better ordering and orientation of both assemblies. In this paper, we formalize this question as the Optimal Syntenic Layout problem, show that it is in general NP-hard, but that it can be solved well in practice using an algorithm based on maximal graph matching. We illustrate the problem using different assemblies of two strains of Bdellovibrio bacteriovorus.

Original language	English
Title of host publication	Proceedings of the German Conference on Bioinformatics, GCB 2004
Editors	Robert Giegerich, Jens Stoye
Publisher	Gesellschaft fur Informatik (GI)
Pages	3-12
Number of pages	10
ISBN (Electronic)	3885793822
Publication status	Published - 2004
Externally published	Yes
Event	2004 German Conference on Bioinformatics, GCB 2004 - Bielefeld, Germany Duration: Oct 4 2004 → Oct 6 2004

Publication series

Name	Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)
Volume	P-53
ISSN (Print)	1617-5468

Conference

Conference	2004 German Conference on Bioinformatics, GCB 2004
Country/Territory	Germany
City	Bielefeld
Period	10/4/04 → 10/6/04

Bibliographical note

Publisher Copyright:
© 2004 Gesellschaft fur Informatik (GI). All rights reserved.

ASJC Scopus Subject Areas

Computer Science Applications

Cite this

Friedrichs, O. D., Halpern, A. L., Lippert, R., Rausch, C., Schuster, S. C., & Huson, D. H. (2004). Syntenic Layout of Two Assemblies of Related Genomes. In R. Giegerich, & J. Stoye (Eds.), Proceedings of the German Conference on Bioinformatics, GCB 2004 (pp. 3-12). (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI); Vol. P-53). Gesellschaft fur Informatik (GI).

Friedrichs, Olaf Delgado ; Halpern, Aaron L. ; Lippert, Ross et al. / Syntenic Layout of Two Assemblies of Related Genomes. Proceedings of the German Conference on Bioinformatics, GCB 2004. editor / Robert Giegerich ; Jens Stoye. Gesellschaft fur Informatik (GI), 2004. pp. 3-12 (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)).

@inproceedings{d9554890e11a4cc5a159bf4a3d792262,

title = "Syntenic Layout of Two Assemblies of Related Genomes",

abstract = "To facilitate research in comparative genomics, sequencing projects are increasingly aimed at assembling the genomes of closely related organisms. Given two incomplete assemblies of two related genomes, the question arises how to use the similarity of the two sequences to obtain a better ordering and orientation of both assemblies. In this paper, we formalize this question as the Optimal Syntenic Layout problem, show that it is in general NP-hard, but that it can be solved well in practice using an algorithm based on maximal graph matching. We illustrate the problem using different assemblies of two strains of Bdellovibrio bacteriovorus.",

author = "Friedrichs, \{Olaf Delgado\} and Halpern, \{Aaron L.\} and Ross Lippert and Christian Rausch and Schuster, \{Stephan C.\} and Huson, \{Daniel H.\}",

note = "Publisher Copyright: {\textcopyright} 2004 Gesellschaft fur Informatik (GI). All rights reserved.; 2004 German Conference on Bioinformatics, GCB 2004 ; Conference date: 04-10-2004 Through 06-10-2004",

year = "2004",

language = "English",

series = "Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)",

publisher = "Gesellschaft fur Informatik (GI)",

pages = "3--12",

editor = "Robert Giegerich and Jens Stoye",

booktitle = "Proceedings of the German Conference on Bioinformatics, GCB 2004",

}

Friedrichs, OD, Halpern, AL, Lippert, R, Rausch, C, Schuster, SC & Huson, DH 2004, Syntenic Layout of Two Assemblies of Related Genomes. in R Giegerich & J Stoye (eds), Proceedings of the German Conference on Bioinformatics, GCB 2004. Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), vol. P-53, Gesellschaft fur Informatik (GI), pp. 3-12, 2004 German Conference on Bioinformatics, GCB 2004, Bielefeld, Germany, 10/4/04.

Syntenic Layout of Two Assemblies of Related Genomes. / Friedrichs, Olaf Delgado; Halpern, Aaron L.; Lippert, Ross et al.
Proceedings of the German Conference on Bioinformatics, GCB 2004. ed. / Robert Giegerich; Jens Stoye. Gesellschaft fur Informatik (GI), 2004. p. 3-12 (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI); Vol. P-53).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Syntenic Layout of Two Assemblies of Related Genomes

AU - Friedrichs, Olaf Delgado

AU - Halpern, Aaron L.

AU - Lippert, Ross

AU - Rausch, Christian

AU - Schuster, Stephan C.

AU - Huson, Daniel H.

PY - 2004

Y1 - 2004

N2 - To facilitate research in comparative genomics, sequencing projects are increasingly aimed at assembling the genomes of closely related organisms. Given two incomplete assemblies of two related genomes, the question arises how to use the similarity of the two sequences to obtain a better ordering and orientation of both assemblies. In this paper, we formalize this question as the Optimal Syntenic Layout problem, show that it is in general NP-hard, but that it can be solved well in practice using an algorithm based on maximal graph matching. We illustrate the problem using different assemblies of two strains of Bdellovibrio bacteriovorus.

AB - To facilitate research in comparative genomics, sequencing projects are increasingly aimed at assembling the genomes of closely related organisms. Given two incomplete assemblies of two related genomes, the question arises how to use the similarity of the two sequences to obtain a better ordering and orientation of both assemblies. In this paper, we formalize this question as the Optimal Syntenic Layout problem, show that it is in general NP-hard, but that it can be solved well in practice using an algorithm based on maximal graph matching. We illustrate the problem using different assemblies of two strains of Bdellovibrio bacteriovorus.

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

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

M3 - Conference contribution

AN - SCOPUS:85134603431

T3 - Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)

SP - 3

EP - 12

BT - Proceedings of the German Conference on Bioinformatics, GCB 2004

A2 - Giegerich, Robert

A2 - Stoye, Jens

PB - Gesellschaft fur Informatik (GI)

T2 - 2004 German Conference on Bioinformatics, GCB 2004

Y2 - 4 October 2004 through 6 October 2004

ER -

Friedrichs OD, Halpern AL, Lippert R, Rausch C, Schuster SC, Huson DH. Syntenic Layout of Two Assemblies of Related Genomes. In Giegerich R, Stoye J, editors, Proceedings of the German Conference on Bioinformatics, GCB 2004. Gesellschaft fur Informatik (GI). 2004. p. 3-12. (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)).

Syntenic Layout of Two Assemblies of Related Genomes

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus Subject Areas

Other files and links

Fingerprint

Cite this