2 Search Results for "Rasche, Florian"


Document
The Graph Motif Problem Parameterized by the Structure of the Input Graph

Authors: Édouard Bonnet and Florian Sikora

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Graph Motif has been analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. Though, in the many applications of Graph Motif, the input graph originates from real-life and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. Interestingly, we establish that Graph Motif is W[1]-hard (while in W[P]) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way.

Cite as

Édouard Bonnet and Florian Sikora. The Graph Motif Problem Parameterized by the Structure of the Input Graph. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 319-330, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2015.319,
  author =	{Bonnet, \'{E}douard and Sikora, Florian},
  title =	{{The Graph Motif Problem Parameterized by the Structure of the Input Graph}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{319--330},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.319},
  URN =		{urn:nbn:de:0030-drops-55937},
  doi =		{10.4230/LIPIcs.IPEC.2015.319},
  annote =	{Keywords: Parameterized Complexity, Structural Parameters, Graph Motif, Computational Biology}
}
Document
Towards de novo identification of metabolites by analyzing tandem mass spectra

Authors: Sebastian Böcker and Florian Rasche

Published in: Dagstuhl Seminar Proceedings, Volume 8101, Computational Proteomics (2008)


Abstract
Mass spectrometry is among the most widely used technologies in proteomics and metabolomics. For metabolites, de novo interpretation of spectra is even more important than for protein data, because metabolite spectra databases cover only a small fraction of naturally occurring metabolites. In this work, we analyze a method for fully automated de novo identification of metabolites from tandem mass spectra. Mass spectrometry data is usually assumed to be insufficient for identification of molecular structures, so we want to estimate the molecular formula of the unknown metabolite, a crucial step for its identification. This is achieved by calculating the possible formulas of the fragment peaks and then reconstructing the most likely fragmentation tree from this information. We present tests on real mass spectra showing that our algorithms solve the reconstruction problem suitably fast and provide excellent results: For all 32 test compounds the correct solution was among the top five suggestions, for 26 compounds the first suggestion of the exact algorithm was correct.

Cite as

Sebastian Böcker and Florian Rasche. Towards de novo identification of metabolites by analyzing tandem mass spectra. In Computational Proteomics. Dagstuhl Seminar Proceedings, Volume 8101, pp. 1-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bocker_et_al:DagSemProc.08101.2,
  author =	{B\"{o}cker, Sebastian and Rasche, Florian},
  title =	{{Towards de novo identification of metabolites by analyzing tandem mass spectra}},
  booktitle =	{Computational Proteomics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8101},
  editor =	{Christian Huber and Oliver Kohlbacher and Michal Linial and Katrin Marcus 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.08101.2},
  URN =		{urn:nbn:de:0030-drops-17839},
  doi =		{10.4230/DagSemProc.08101.2},
  annote =	{Keywords: Tandem mass spectrometry, metabolomics, de novo interpretation}
}
  • Refine by Author
  • 1 Bonnet, Édouard
  • 1 Böcker, Sebastian
  • 1 Rasche, Florian
  • 1 Sikora, Florian

  • Refine by Classification

  • Refine by Keyword
  • 1 Computational Biology
  • 1 Graph Motif
  • 1 Parameterized Complexity
  • 1 Structural Parameters
  • 1 Tandem mass spectrometry
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail