3 Search Results for "Tholey, Andreas"

Document
DOI: 10.4230/LIPIcs.ESA.2025.39
Going Beyond Surfaces in Diameter Approximation

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+ε)-approximation algorithms with running time poly(1/ε, log n)⋅ n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+ε)-approximation algorithms with the following running times: - 𝒪_h((1/ε)^𝒪(h) ⋅ nlog² n)-time algorithm for graphs excluding an apex graph of size h as a minor, - 𝒪_d((1/ε)^𝒪(d) ⋅ nlog² n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+ε)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time 𝒪_h((1/ε)⁸⋅ nlog nlog W) and query time 𝒪_h((1/ε)²⋅log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.
Cite as

Michał Włodarczyk. Going Beyond Surfaces in Diameter Approximation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.ESA.2025.39,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Going Beyond Surfaces in Diameter Approximation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.39},
  URN =		{urn:nbn:de:0030-drops-245076},
  doi =		{10.4230/LIPIcs.ESA.2025.39},
  annote =	{Keywords: diameter, approximation, distance oracles, graph minors, treewidth}
}
Document
DOI: 10.4230/OASIcs.GCB.2013.56
Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics

Authors: Anna Katharina Hildebrandt, Ernst Althaus, Hans-Peter Lenhof, Chien-Wen Hung, Andreas Tholey, and Andreas Hildebrandt

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013

Abstract
Mass spectrometry is the major analytical tool for the identification and quantification of proteins in biological samples. In so-called top-down proteomics, separation and mass spectrometric analysis is performed at the level of intact proteins, without preparatory digestion steps. It has been shown that the tandem mass tag (TMT) labeling technology, which is often used for quantification based on digested proteins (bottom-up studies), can be applied in top-down proteomics as well. This, however, leads to a complex interpretation problem, where we need to annotate measured peaks with their respective generating protein, the number of charges, and the a priori unknown number of TMT-groups attached to this protein. In this work, we give an algorithm for the efficient enumeration of all valid annotations that fulfill available experimental constraints. Applying the algorithm to real-world data, we show that the annotation problem can indeed be efficiently solved. However, our experiments also demonstrate that reliable annotation in complex mixtures requires at least partial sequence information and high mass accuracy and resolution to go beyond the proof-of-concept stage.
Cite as

Anna Katharina Hildebrandt, Ernst Althaus, Hans-Peter Lenhof, Chien-Wen Hung, Andreas Tholey, and Andreas Hildebrandt. Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 56-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{hildebrandt_et_al:OASIcs.GCB.2013.56,
  author =	{Hildebrandt, Anna Katharina and Althaus, Ernst and Lenhof, Hans-Peter and Hung, Chien-Wen and Tholey, Andreas and Hildebrandt, Andreas},
  title =	{{Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{56--67},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.56},
  URN =		{urn:nbn:de:0030-drops-42304},
  doi =		{10.4230/OASIcs.GCB.2013.56},
  annote =	{Keywords: Mass spectrometry, TMT labeling, Top-down Proteomics}
}
Document
DOI: 10.4230/DagSemProc.05471.10
MALDI Mass Spectrometry for Quantitative Proteomics – Approaches, Scopes and Limitations

Authors: Andreas Tholey

Published in: Dagstuhl Seminar Proceedings, Volume 5471, Computational Proteomics (2006)

Abstract
The determination of absolute protein amounts and the quantification of differentially expressed proteins belong to the most important goals in proteomics. Despite being one of the key technologies for the identification of proteins, the application of matrix assisted laser desorption/ionization (MALDI) mass spectrometry (MS) for quantitative analyses is hampered by several inherent factors. The goal of the present paper is to outline these difficulties but also to present some selected approaches which enable MALDI MS to be used for the quantification of biomolecules. In particular, methods for the improvement of the homogeneity of MALDI samples and the use of internal standards for the relative quantification are discussed. Strategies for in-vivo and in-vitro labelling of peptides and proteins with stable isotopes are presented. The need for guidelines for the presentation and evaluation of data as well as for bioinformatical approaches for the interpretation of quantitative data will be addressed.
Cite as

Andreas Tholey. MALDI Mass Spectrometry for Quantitative Proteomics – Approaches, Scopes and Limitations. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 5471, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{tholey:DagSemProc.05471.10,
  author =	{Tholey, Andreas},
  title =	{{MALDI Mass Spectrometry for Quantitative Proteomics – Approaches, Scopes and Limitations}},
  booktitle =	{Computational Proteomics},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5471},
  editor =	{Christian G. Huber and Oliver Kohlbacher and Knut Reinert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05471.10},
  URN =		{urn:nbn:de:0030-drops-5367},
  doi =		{10.4230/DagSemProc.05471.10},
  annote =	{Keywords: MALDI, mass spectrometry, quantification, ionic liquid matrices}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2013
  • 1 2006

  • Refine by Author
  • 2 Tholey, Andreas
  • 1 Althaus, Ernst
  • 1 Hildebrandt, Andreas
  • 1 Hildebrandt, Anna Katharina
  • 1 Hung, Chien-Wen
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 MALDI
  • 1 Mass spectrometry
  • 1 TMT labeling
  • 1 Top-down Proteomics
  • 1 approximation
  • Show More...

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