DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2025.1

Polymorphic Cycle Basis in a Sequence of Graphs to Analyze the Structural Evolution of a Molecular Dynamic Trajectory

Authors: Ylène Aboulfath, Dominique Barth, Thierry Mautor, Dimitri Watel, and Marc-Antoine Weisser

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

Molecular dynamics analysis is a fundamental topic in chemistry, in particular the study of the formation and dissolution of hydrogen bonds over time. The dynamics of these bonds create and break cycles which are crucial to the structure of the molecules. The challenge in cycle analysis is twofold: there is an exponential number of cycles, and some cycles are very close. We introduce a graph-based approach using minimum cycle bases to assist in molecular dynamics analysis. Given a set of graphs representing a molecule trajectory, we determine, for each graph, a minimum cycle basis and construct a graph of cycles which represents the cycles of minimum bases and their interactions. Then, we aggregate all information from these graphs of cycles into a polygraph. Each vertex of the polygraph represents a class of cycles appearing in different minimum bases and playing equivalent roles in the trajectory. This paper introduces our approach, establishes the complexity of associated problems, and suggests an implementation. Simulations are conducted on both real and generated data to evaluate the performance of our approach.

Cite as

Ylène Aboulfath, Dominique Barth, Thierry Mautor, Dimitri Watel, and Marc-Antoine Weisser. Polymorphic Cycle Basis in a Sequence of Graphs to Analyze the Structural Evolution of a Molecular Dynamic Trajectory. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aboulfath_et_al:LIPIcs.SEA.2025.1,
  author =	{Aboulfath, Yl\`{e}ne and Barth, Dominique and Mautor, Thierry and Watel, Dimitri and Weisser, Marc-Antoine},
  title =	{{Polymorphic Cycle Basis in a Sequence of Graphs to Analyze the Structural Evolution of a Molecular Dynamic Trajectory}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.1},
  URN =		{urn:nbn:de:0030-drops-232399},
  doi =		{10.4230/LIPIcs.SEA.2025.1},
  annote =	{Keywords: Graph theory, Cycle basis, Molecular analysis}
}

Search Results

Documents authored by Weisser, Marc-Antoine

Polymorphic Cycle Basis in a Sequence of Graphs to Analyze the Structural Evolution of a Molecular Dynamic Trajectory

Abstract

Cite as

Thanks for your feedback!

Could not send message