Search Results

Documents authored by Stadler, Peter F.

Document
DOI: 10.4230/LIPIcs.WABI.2025.12
Extension of Partial Atom-To-Atom Maps: Uniqueness and Algorithms

Authors: Marcos E. González Laffitte, Tieu-Long Phan, and Peter F. Stadler

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Chemical reaction databases typically report the molecular structures of reactant and product compounds, as well as their stoichiometry, but lack information, in particular, on the correspondence of reactant and product atoms. These atom-to-atom maps (AAM), however, are crucial for applications including chemical synthesis planning in organic chemistry and the analysis of isotope labeling experiments in modern metabolomics. AAMs therefore need to be reconstructed computationally. This situation is aggravated, furthermore, by the fact that chemically correct AAMs are, fundamentally, determined by quantum-mechanical phenomena and thus cannot be reliably computed by solving graph-theoretical optimization problems defined by the reactant and product structures. A viable solution for this problem is to shift the focus into first identifying a partial AAM containing the reaction center, i.e., covering the atoms incident with all bonds that change during a reaction. This then leads to the problem of extending the partial map to the full reaction. The AAM of a reaction is faithfully represented by the Imaginary Transition State (ITS) graph, providing a convenient graph-theoretic framework to address the questions of when and how a partial AAM can be extended. We show that an unique extension exists whenever, and only if, these partial AAMs cover the reaction center. In this case their extension can be computed by solving a constrained graph-isomorphism search between specific subgraphs of ITS graphs. We close by benchmarking different tools for this task.
Cite as

Marcos E. González Laffitte, Tieu-Long Phan, and Peter F. Stadler. Extension of Partial Atom-To-Atom Maps: Uniqueness and Algorithms. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 12:1-12:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gonzalezlaffitte_et_al:LIPIcs.WABI.2025.12,
  author =	{Gonz\'{a}lez Laffitte, Marcos E. and Phan, Tieu-Long and Stadler, Peter F.},
  title =	{{Extension of Partial Atom-To-Atom Maps: Uniqueness and Algorithms}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{12:1--12:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.12},
  URN =		{urn:nbn:de:0030-drops-239410},
  doi =		{10.4230/LIPIcs.WABI.2025.12},
  annote =	{Keywords: atom-to-atom maps, imaginary transition state (ITS) graphs, condensed graph of the reaction (CGR), chemical reaction mechanisms, molecular graphs, metabolic networks, chemical synthesis planning, constrained graph isomorphism}
}
Document
DOI: 10.4230/LIPIcs.WABI.2020.10
Economic Genome Assembly from Low Coverage Illumina and Nanopore Data

Authors: Thomas Gatter, Sarah von Löhneysen, Polina Drozdova, Tom Hartmann, and Peter F. Stadler

Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)

Abstract
Ongoing developments in genome sequencing have caused a fundamental paradigm shift in the field in recent years. With ever lower sequencing costs, projects are no longer limited by available raw data, but rather by computational demands. The high complexity of eukaryotic genomes in concordance with increasing data sizes creates unique demands on methods to assemble full genomes. We describe a new approach to assemble genomes from a combination of low-coverage short and long reads. LazyB starts from a bipartite overlap graph between long reads and restrictively filtered short-read unitigs, which are then reduced to a long-read overlap graph G. Instead of the more conventional approach of removing tips, bubbles, and other local features, LazyB stepwisely extracts subgraphs whose global properties approach a disjoint union of paths. First, a consistently oriented subgraph is extracted, which in a second step is reduced to a directed acyclic graph. In the next step, properties of proper interval graphs are used to extract contigs as maximum weight paths. These are translated into genomic sequences only in the final step. A prototype implementation of LazyB, entirely written in python, not only yields significantly more accurate assemblies of the yeast and fruit fly genomes compared to state-of-the-art pipelines but also requires much less computational effort. Our findings demonstrate a new low-cost method that enables the assembly of even large genomes with low computational effort.
Cite as

Thomas Gatter, Sarah von Löhneysen, Polina Drozdova, Tom Hartmann, and Peter F. Stadler. Economic Genome Assembly from Low Coverage Illumina and Nanopore Data. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gatter_et_al:LIPIcs.WABI.2020.10,
  author =	{Gatter, Thomas and von L\"{o}hneysen, Sarah and Drozdova, Polina and Hartmann, Tom and Stadler, Peter F.},
  title =	{{Economic Genome Assembly from Low Coverage Illumina and Nanopore Data}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Kingsford, Carl and Pisanti, Nadia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.10},
  URN =		{urn:nbn:de:0030-drops-127991},
  doi =		{10.4230/LIPIcs.WABI.2020.10},
  annote =	{Keywords: Nanopore sequencing, Illumina sequencing, genome assembly, spanning tree, unitigs, anchors}
}
Document
DOI: 10.4230/DagRep.7.11.28
Algorithmic Cheminformatics (Dagstuhl Seminar 17452)

Authors: Jakob L. Andersen, Christoph Flamm, Daniel Merkle, and Peter F. Stadler

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
Dagstuhl Seminar 17452 "Algorithmic Cheminformatics" brought together leading researchers from both chemistry and computer science. The seminar was the second in a series of the Dagstuhl seminars and had a focus on concurrency theory as chemical systems are highly concurrent by nature. Within computer science we focused on formal approaches for chemistry and concurrency theory, including process calculi and Petri nets. The participants surveyed areas of overlapping interests and identified possible fields of joint future research.
Cite as

Jakob L. Andersen, Christoph Flamm, Daniel Merkle, and Peter F. Stadler. Algorithmic Cheminformatics (Dagstuhl Seminar 17452). In Dagstuhl Reports, Volume 7, Issue 11, pp. 28-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{andersen_et_al:DagRep.7.11.28,
  author =	{Andersen, Jakob L. and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  title =	{{Algorithmic Cheminformatics (Dagstuhl Seminar 17452)}},
  pages =	{28--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Andersen, Jakob L. and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.11.28},
  URN =		{urn:nbn:de:0030-drops-86692},
  doi =		{10.4230/DagRep.7.11.28},
  annote =	{Keywords: Modelling, Simulation, Networks, Semantics / Formal Methods}
}
Document
DOI: 10.4230/LIPIcs.WABI.2017.17
Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps

Authors: Nikolai Nojgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract
Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to event-labeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V(S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. The algorithms are implemented in C++ using the boost graph library and are freely available at https://github.com/Nojgaard/tc-recon. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with hor- izontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems.
Cite as

Nikolai Nojgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth. Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nojgaard_et_al:LIPIcs.WABI.2017.17,
  author =	{Nojgaard, Nikolai and Gei{\ss}, Manuela and Merkle, Daniel and Stadler, Peter F. and Wieseke, Nicolas and Hellmuth, Marc},
  title =	{{Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.17},
  URN =		{urn:nbn:de:0030-drops-76362},
  doi =		{10.4230/LIPIcs.WABI.2017.17},
  annote =	{Keywords: Tree Reconciliation, Horizontal Gene Transfer, Reconciliation Map, Time-Consistency, History of gene families}
}
Document
DOI: 10.4230/DagRep.4.11.22
Algorithmic Cheminformatics (Dagstuhl Seminar 14452)

Authors: Wolfgang Banzhaf, Christoph Flamm, Daniel Merkle, and Peter F. Stadler

Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)

Abstract
Dagstuhl Seminar 14452 "Algorithmic Cheminformatics" brought together leading researchers from both chemistry and computer science. The meeting successfully aimed at bridging in the apparent gap between the two disciplines. The participants surveyed areas of overlapping interests and identified possible fields of joint future research.
Cite as

Wolfgang Banzhaf, Christoph Flamm, Daniel Merkle, and Peter F. Stadler. Algorithmic Cheminformatics (Dagstuhl Seminar 14452). In Dagstuhl Reports, Volume 4, Issue 11, pp. 22-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{banzhaf_et_al:DagRep.4.11.22,
  author =	{Banzhaf, Wolfgang and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  title =	{{Algorithmic Cheminformatics (Dagstuhl Seminar 14452)}},
  pages =	{22--39},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{11},
  editor =	{Banzhaf, Wolfgang and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.11.22},
  URN =		{urn:nbn:de:0030-drops-49686},
  doi =		{10.4230/DagRep.4.11.22},
  annote =	{Keywords: Graph Transformation Systems, Graph and Hypergraph Invariants, Graph Comparison, Network Flows, Hypergraphs, Formal Languages, Algebraic Chemistry}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact