The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins

François Anton; Thomas Hamelryck

doi:10.1109/ISVD.2009.40

The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins

François Anton (Invited author)
, Thomas Hamelryck (Invited author)

University of Copenhagen

Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research

1 Downloads (Orbit)

Abstract

The calculation of the overlap volume of half-spheres or ellipsoids is of direct interest in structural bioinformatics, which is concerned with the computational study of biological macromolecules on a genomic scale. We present an algorithm for computing the Delaunay graph and the overlap volume of a set of half-balls using exact predicates that detect the disjointness or non-disjointness of two half-balls and the validity of the generalized Voronoi vertex of four half-balls using geometric invariants and action (multiplication map) matrices. We prove the correctness of the algorithm and the optimality of the degree of the predicates by using geometric invariants and GroÂ¿bner bases. The main application of these certified computations is to predict the 3D structure of proteins.

Original language	English
Title of host publication	Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering
Number of pages	278
Place of Publication	DTU-Informatics
Publisher	IEEE Computer Society Press
Publication date	2009
Pages	263-264
ISBN (Print)	978-97-643-0497-8
DOIs	https://doi.org/10.1109/ISVD.2009.40
Publication status	Published - 2009
Event	6th International Symposium on Voronoi Diagrams in Science and Engineering - Technical University of Denmark, Kgs. Lyngby, Denmark Duration: 23 Jun 2009 → 26 Jun 2009 Conference number: 6 http://www2.imm.dtu.dk/projects/ISVD/

Conference

Conference	6th International Symposium on Voronoi Diagrams in Science and Engineering
Number	6
Location	Technical University of Denmark
Country/Territory	Denmark
City	Kgs. Lyngby
Period	23/06/2009 → 26/06/2009
Internet address	http://www2.imm.dtu.dk/projects/ISVD/

Bibliographical note

Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Access to Document

10.1109/ISVD.2009.40

OpenUrl availability

Check availability in DTU Findit

Cite this

@inbook{cd59a5c5721b4828b832a15e59b15534,

title = "The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins",

abstract = "The calculation of the overlap volume of half-spheres or ellipsoids is of direct interest in structural bioinformatics, which is concerned with the computational study of biological macromolecules on a genomic scale. We present an algorithm for computing the Delaunay graph and the overlap volume of a set of half-balls using exact predicates that detect the disjointness or non-disjointness of two half-balls and the validity of the generalized Voronoi vertex of four half-balls using geometric invariants and action (multiplication map) matrices. We prove the correctness of the algorithm and the optimality of the degree of the predicates by using geometric invariants and Gro{\^A}¿bner bases. The main application of these certified computations is to predict the 3D structure of proteins.",

author = "Fran{\c c}ois Anton and Thomas Hamelryck",

note = "Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.; 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 ; Conference date: 23-06-2009 Through 26-06-2009",

year = "2009",

doi = "10.1109/ISVD.2009.40",

language = "English",

isbn = "978-97-643-0497-8",

pages = "263--264",

booktitle = "Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering",

publisher = "IEEE Computer Society Press",

url = "http://www2.imm.dtu.dk/projects/ISVD/",

}

Anton, F & Hamelryck, T 2009, The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins. in Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering. IEEE Computer Society Press, DTU-Informatics, pp. 263-264, 6th International Symposium on Voronoi Diagrams in Science and Engineering, Kgs. Lyngby, Denmark, 23/06/2009. https://doi.org/10.1109/ISVD.2009.40

The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins. / Anton, François (Invited author); Hamelryck, Thomas (Invited author).
Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering. DTU-Informatics: IEEE Computer Society Press, 2009. p. 263-264.

Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research

TY - ABST

T1 - The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins

AU - Anton, François

AU - Hamelryck, Thomas

N1 - Conference code: 6

PY - 2009

Y1 - 2009

N2 - The calculation of the overlap volume of half-spheres or ellipsoids is of direct interest in structural bioinformatics, which is concerned with the computational study of biological macromolecules on a genomic scale. We present an algorithm for computing the Delaunay graph and the overlap volume of a set of half-balls using exact predicates that detect the disjointness or non-disjointness of two half-balls and the validity of the generalized Voronoi vertex of four half-balls using geometric invariants and action (multiplication map) matrices. We prove the correctness of the algorithm and the optimality of the degree of the predicates by using geometric invariants and GroÂ¿bner bases. The main application of these certified computations is to predict the 3D structure of proteins.

AB - The calculation of the overlap volume of half-spheres or ellipsoids is of direct interest in structural bioinformatics, which is concerned with the computational study of biological macromolecules on a genomic scale. We present an algorithm for computing the Delaunay graph and the overlap volume of a set of half-balls using exact predicates that detect the disjointness or non-disjointness of two half-balls and the validity of the generalized Voronoi vertex of four half-balls using geometric invariants and action (multiplication map) matrices. We prove the correctness of the algorithm and the optimality of the degree of the predicates by using geometric invariants and GroÂ¿bner bases. The main application of these certified computations is to predict the 3D structure of proteins.

U2 - 10.1109/ISVD.2009.40

DO - 10.1109/ISVD.2009.40

M3 - Conference abstract in proceedings

SN - 978-97-643-0497-8

SP - 263

EP - 264

BT - Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering

PB - IEEE Computer Society Press

CY - DTU-Informatics

T2 - 6th International Symposium on Voronoi Diagrams in Science and Engineering

Y2 - 23 June 2009 through 26 June 2009

ER -

The Voronoi diagram of half-balls and its application to the prediction of the 3D structure of proteins

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this