| Publications of Clemens Gröpl | [download BiBTeX file] [back to main page] |
| Bodirsky, M., Gröpl, C. & Kang, M. (2008), "Generating unlabeled connected cubic planar graphs uniformly at random", Random Structures and Algorithms. Vol. 32(2), pp. 157-180. |
| Abstract: We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted connected cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for the exact number of rooted cubic planar graphs. This leads to rooted 3-connected cubic planar graphs, which have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense-reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted 3-connected cubic planar graphs with given symmetries. Colored networks can again be decomposed along the connectivity structure. For rooted 3-connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. Since all these numbers can be evaluated in polynomial time using dynamic programming, rooted connected cubic planar graphs can be generated uniformly at random in polynomial time by inverting the decomposition along the connectivity structure. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm |
BibTeX:
@article{BGK07b,
author = {Manuel Bodirsky and Clemens Gröpl and Mihyun Kang},
title = {Generating unlabeled connected cubic planar graphs uniformly at random},
journal = {Random Structures and Algorithms},
year = {2008},
volume = {32},
number = {2},
pages = {157-180},
doi = {http://dx.doi.org/10.1002/rsa.20206}
}
|
| Gröpl, C. (2008), "Habilitationsschrift". School: Free University Berlin. |
| Abstract: Dokumente zum (kumulativen) Habilitationsverfahren von Dr. Clemens Gröpl an der Freien Universität Berlin. Das Gesamtthema der publizierten Forschungsergebnisse gemäß §2.I.(c) der Habilitationsordnung des Fachbereiches Mathematik und Informatik der Freien Universität Berlin (veröffentlicht im Amtsblatt der Freien Universität Berlin, 4.10.1999. Ausgabe Nr. 2311999) lautet: "Untersuchungen zum Steinerbaumproblem in Graphen, zur Enumeration zufälliger planarer Graphen, und zu Algorithmen in der massenspektrometrie-basierten Proteomik." - Antrag - Erklärung - Summary of Publications for Habilitation - Sechzehn Originalarbeiten (bitte Copyright beachten!) Das Habilitationsverfahren wurde am 09.07.2009 eröffnet. |
BibTeX:
@phdthesis{Habilitation-Groepl,
author = {Clemens Gröpl},
title = {Habilitationsschrift},
school = {Free University Berlin},
year = {2008}
}
|
| Lange, E., Tautenhahn, R., Neumann, S. & Gröpl, C. (2008), "Critical assessment of alignment procedures for LC-MS proteomics and metabolomic measurements", BMC Bioinformatics. Vol. 9(375) |
| Abstract: Background Liquid chromatography coupled to mass spectrometry (LC-MS) has become a prominent tool for the analysis of complex proteomics and metabolomics samples. In many applications multiple LC-MS measurements need to be compared, e. g. to improve reliability or to combine results from different samples in a statistical comparative analysis. As in all physical experiments, LC-MS data are affected by uncertainties, and variability of retention time is encountered in all data sets. It is therefore necessary to estimate and correct the underlying distortions of the retention time axis to search for corresponding compounds in different samples. To this end, a variety of so-called LC-MS map alignment algorithms have been developed during the last four years. Most of these approaches are well documented, but they are usually evaluated on very specific samples only. So far, no publication has been assessing different alignment algorithms using a standard LC-MS sample along with commonly used quality criteria. Results We propose two LC-MS proteomics as well as two LC-MS metabolomics data sets that represent typical alignment scenarios. Furthermore, we introduce a new quality measure for the evaluation of LC-MS alignment algorithms. Using the four data sets to compare six freely available alignment algorithms proposed for the alignment of metabolomics and proteomics LC-MS measurements, we found significant differences with respect to alignment quality, running time, and usability in general. Conclusion The multitude of available alignment methods necessitates the generation of standard data sets and quality measures that allow users as well as developers to benchmark and compare their map alignment tools on a fair basis. Our study represents a first step in this direction. Currently, the installation and evaluation of the "correct" parameter settings can be quite a time-consuming task, and the success of a particular method is still highly dependent on the experience of the user. Therefore, we propose to continue and extend this type of study to a community-wide competition. All data as well as our evaluation scripts are available at http://msbi.ipb-halle.de/msbi/caap webcite. |
BibTeX:
@article{LTNG08,
author = {Eva Lange and Ralf Tautenhahn and Steffen Neumann and Clemens Gröpl},
title = {Critical assessment of alignment procedures for LC-MS proteomics and metabolomic measurements},
journal = {BMC Bioinformatics},
year = {2008},
volume = {9},
number = {375},
url = {http://www.biomedcentral.com/1471-2105/9/375},
doi = {http://dx.doi.org/10.1186/1471-2105-9-375}
}
|
| Schulz-Trieglaff, O., Hussong, R., Gröpl, C., Leinenbach, A., Hildebrandt, A., Huber, C. & Reinert, K. (2008), "Computational Quantification of Peptides from LC-MS data", Journal of Computational Biology. Vol. 15(7), pp. 685-704. |
| Abstract: Liquid chromatography coupled to mass spectrometry (LC-MS) has become a major tool for the study of biological processes. High-throughput LC-MS experimentsare frequently conducted in modern laboratories, generating an enormous amountof data per day. A manual inspection is therefore no longer a feasible task. Consequently, there is a need for computational tools that can rapidly provide informationabout mass, elution time, and abundance of the compounds in a LC-MS sample. Wepresent an algorithm for the detection and quantification of peptides in LC-MS data. Our approach is flexible and independent of the MS technology in use. It is basedon a combination of the sweep line paradigm with a novel wavelet function tailoredto detect isotopic patterns of peptides. We propose a simple voting schema to usethe redundant information in consecutive scans for an accurate determination ofmonoisotopic masses and charge states. By explicitly modeling the instrument inaccuracy, we are also able to cope with data sets of different quality and resolution.We evaluate our technique on data from different instruments and show that we canrapidly estimate mass, centroid of retention time and abundance of peptides in a sound algorithmic framework. Finally, we compare the performance of our method to several other techniques on three data sets of varying complexity. |
BibTeX:
@article{SHGLHHR07,
author = {Ole Schulz-Trieglaff and Rene Hussong and Clemens Gröpl and Andreas Leinenbach and Andreas Hildebrandt and Christian Huber and Knut Reinert},
title = {Computational Quantification of Peptides from LC-MS data},
journal = {Journal of Computational Biology},
year = {2008},
volume = {15},
number = {7},
pages = {685-704},
url = {http://dx.doi.org/10.1089/cmb.2007.0117},
doi = {http://dx.doi.org/10.1089/cmb.2007.0117}
}
|
| Schulz-Trieglaff, O., Pfeifer, N., Gröpl, C., Kohlbacher, O. & Reinert, K. (2008), "LC-MSsim - a simulation software for liquid chromatography mass spectrometry data", BMC Bioinformatics. Vol. 9(423) |
| Abstract: BACKGROUND: Mass Spectrometry coupled to Liquid Chromatography (LC-MS) is commonly used to analyze the protein content of biological samples in large scale studies. The data resulting from an LC-MS experiment is huge, highly complex and noisy. Accordingly, it has sparked new developments in Bioinformatics, especially in the fields of algorithm development, statistics and software engineering. In a quantitative label-free mass spectrometry experiment, crucial steps are the detection of peptide features in the mass spectra and the alignment of samples by correcting for shifts in retention time. At the moment, it is difficult to compare the plethora of algorithms for these tasks. So far, curated benchmark data exists only for peptide identification algorithms but no data that represents a ground truth for the evaluation of feature detection, alignment and filtering algorithms. RESULTS: We present LC-MSsim, a simulation software for LC-ESI-MS experiments. It simulates ESI spectra on the MS level. It reads a list of proteins from a FASTA file and digests the protein mixture using a user-defined enzyme. The software creates an LC-MS data set using a predictor for the retention time of the peptides and a model for peak shapes and elution profiles of the mass spectral peaks. Our software also offers the possibility to add contaminants, to change the background noise level and includes a model for the detectability of peptides in mass spectra. After the simulation, LC-MSsim writes the simulated data to public XML formats (mzXML or mzData). The software also stores the positions (monoisotopic m/z and retention time) and ion counts of the simulated ions in separate files. CONCLUSIONS: LC-MSsim generates simulated LC-MS data sets and incorporates models for peak shapes and contaminations. Algorithm developers can match the results of feature detection and alignment algorithms against the simulated ion lists and meaningful error rates can be computed. We anticipate that LC-MSsim will be useful to the wider community to perform benchmark studies and comparisons between computational tools. |
BibTeX:
@article{TPGKR08,
author = {Ole Schulz-Trieglaff and Nico Pfeifer and Clemens Gröpl and Oliver Kohlbacher and Knut Reinert },
title = {LC-MSsim - a simulation software for liquid chromatography mass spectrometry data},
journal = {BMC Bioinformatics},
year = {2008},
volume = {9},
number = {423},
url = {http://dx.doi.org/10.1186/1471-2105-9-423},
doi = {http://dx.doi.org/10.1186/1471-2105-9-423}
}
|
| Sturm, M., Bertsch, A., Gröpl, C., Hildebrandt, A., Hussong, R., Lange, E., Pfeifer, N., Schulz-Trieglaff, O., Zerck, A., Reinert, K. & Kohlbacher, O. (2008), "OpenMS - An open-source software framework for mass spectrometry", BMC Bioinformatics. Vol. 9(163) |
| Abstract: BACKGROUND: Mass spectrometry is an essential analytical technique for high-throughput analysis in proteomics and metabolomics. The development of new separation techniques, precise mass analyzers and experimental protocols is a very active field of research. This leads to more complex experimental setups yielding ever increasing amounts of data. Consequently, analysis of the data is currently often the bottleneck for experimental studies. Although software tools for many data analysis tasks are available today, they are often hard to combine with each other or not flexible enough to allow for rapid prototyping of a new analysis workflow. RESULTS: We present OpenMS, a software framework for rapid application development in mass spectrometry. OpenMS has been designed to be portable, easy-to-use and robust while offering a rich functionality ranging from basic data structures to sophisticated algorithms for data analysis. This has already been demonstrated in several studies. CONCLUSIONS: OpenMS is available under the Lesser GNU Public License (LGPL) from the project website at http://www.openms.de. |
BibTeX:
@article{SBGHHLPTZRK08,
author = {Marc Sturm and Andreas Bertsch and Clemens Gröpl and Andreas Hildebrandt and Rene Hussong and Eva Lange and Nico Pfeifer and Ole Schulz-Trieglaff and Alexandra Zerck and Knut Reinert and Oliver Kohlbacher},
title = {OpenMS - An open-source software framework for mass spectrometry},
journal = {BMC Bioinformatics},
year = {2008},
volume = {9},
number = {163},
url = {http://dx.doi.org/10.1186/1471-2105-9-163},
doi = {http://dx.doi.org/10.1186/1471-2105-9-163}
}
|
| Bodirsky, M., Gröpl, C., Johannsen, D. & Kang, M. (2007), "A direct decomposition of 3-connected planar graphs", Séminaire Lotharingien de Combinatoire., In Proceedings of the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05). Taormina Vol. B54Ak, pp. 15 pages. |
| Abstract: Abstract. We present a decomposition strategy for c-nets, i.e., rooted 3-connected planar maps. The decomposition yields an algebraic equation for the number of c-nets with a given number of vertices and a given size of the outer face. The decomposition also leads to a deterministic and polynomial time algorithm to sample c-nets uniformly at random. Using rejection sampling, we can also sample isomorphism types of convex polyhedra, i.e., 3-connected planar graphs, uniformly at random. Résumé. Nous proposons une stratégie de décomposition pour les cartes pointées 3-connexes (c-réseaux). Cette décomposition permet d'obtenir une équation algébrique pour le nombre de c-réseaux suivant le nombre de sommets et la taille de la face extèrieure. On en déduit un algorithme de complexité en temps polynomiale pour le tirage aléatoire uniforme des c-réseaux. En utilisant une méthode à rejet, nous obtenons aussi un algorithme de tirage aléatoire uniforme pour les graphes planaires 3-connexes. |
BibTeX:
@article{BGJK07,
author = {Manuel Bodirsky and Clemens Gröpl and Daniel Johannsen and Mihyun Kang},
title = {A direct decomposition of 3-connected planar graphs},
booktitle = {Proceedings of the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05)},
journal = {Séminaire Lotharingien de Combinatoire},
year = {2007},
volume = {B54Ak},
pages = {15 pages}
}
|
| Bodirsky, M., Gröpl, C. & Kang, M. (2007), "Generating labeled planar graphs uniformly at random", Theoretical Computer Science. Vol. 379(3), pp. 377-386. |
| Abstract: We present a deterministic polynomial time algorithm to sample a labeled planar graph uniformly at random. Our approach uses recursive formulae for the exact number of labeled planar graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. We can then use known sampling algorithms and counting formulae for 3-connected planar graphs. |
BibTeX:
@article{BGK07,
author = {Manuel Bodirsky and Clemens Gröpl and Mihyun Kang},
title = {Generating labeled planar graphs uniformly at random},
journal = {Theoretical Computer Science},
year = {2007},
volume = {379},
number = {3},
pages = {377-386},
url = {http://www.sciencedirect.com/science/article/B6V1G-4N4PY45-5/2 /4c06fbabe635c3a288cbf0427e0b395d}
}
|
| Lange, E., Gröpl, C., Schulz-Trieglaff, O., Leinenbach, A., Huber, C. & Reinert, K. (2007), "A Geometric Approach for the Alignment of Liquid Chromatography-Mass Spectrometry Data", In Proceedings of the 15th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB) & 6th European Conference on Computational Biology (ECCB). |
| Abstract: Motivation: Liquid chromatography coupled to mass spectrometry (LC-MS) and combined with tandem mass spectrometry (LC-MS/MS) have become a prominent tool for the analysis of complex proteomic samples. An important step in a typical workflow is the combination of results from multiple LC-MS experiments to improve confidence in the obtained measurements or to compare results from different samples. To do so, a suitable mapping or alignment between the data sets needs to be estimated. The alignment has to correct for variations in mass and elution time which are present in all mass spectrometry experiments. Results: We propose a novel algorithm to align LC-MS samples and to match corresponding ion species across samples. Our algorithm matches landmark signals between two data sets using a geometric technique based on pose clustering. Variations in mass and retention time are corrected by an affine dewarping function estimated from matched landmarks. We use the pairwise dewarping in an algorithm for aligning multiple samples. We show that our pose clustering approach is fast and reliable as compared to previous approaches. It is robust in the presence of noise and able to accurately align samples with only few common ion species. In addition, we can easily handle different kinds of LC-MS data and adopt our algorithm to new mass spectrometry technologies. Availability: This algorithm is implemented as part of the OpenMS software library for shotgun proteomics and available under the Lesser GNU Public License (LGPL) at www.openms.de |
BibTeX:
@inproceedings{Lange_MapAlignment07,
author = {Eva Lange and Clemens Gröpl and Ole Schulz-Trieglaff and Andreas Leinenbach and Christian Huber and Knut Reinert},
title = {A Geometric Approach for the Alignment of Liquid Chromatography-Mass Spectrometry Data},
booktitle = {Proceedings of the 15th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB) & 6th European Conference on Computational Biology (ECCB)},
year = {2007}
}
|
| Meier, C. (2007), "Bioinformatik: Aktuelle Proteinausstattung erlaubt Aussagen über den Gesundheitszustand. Software hilft Ärzten künftig bei der Diagnose.", VDI Nachrichten. 22. Juni, 2007. |
| Abstract: Der Artikel eines freien Medienjournalisten beschreibt den Einsatz von OpenMS in der Proteomik. |
BibTeX:
@misc{VDINachrichten07,
author = {Christian Meier},
title = {Bioinformatik: Aktuelle Proteinausstattung erlaubt Aussagen über den Gesundheitszustand. Software hilft Ärzten künftig bei der Diagnose.},
howpublished = {VDI Nachrichten},
year = {2007},
note = {Der Artikel eines freien Medienjournalisten beschreibt den Einsatz von OpenMS in der Proteomik}
}
|
| Schulz-Trieglaff, O., Hussong, R., Gröpl, C., Hildebrandt, A. & Reinert, K. (2007), "A Fast and Accurate Algorithm for the Quantification of Peptides from Mass Spectrometry data", In Proceedings of the Eleventh Annual International Conference on Research in Computational Molecular Biology (RECOMB 2007)., pp. 473-487. |
| Abstract: Liquid chromatography combined with mass spectrometry (LC-MS) has become the prevalent technology in high-throughput proteomics research. One of the aims of this discipline is to obtain accurate quantitative information about all proteins and peptides in a biological sample. Due to size and complexity of the data generated in these experiments, this problem remains a challenging task requiring sophisticated and efficient computational tools. We propose an algorithm that can quantify even low abundance peptides from LC-MS data. Our approach is flexible and can be applied to preprocessed and raw instrument data. It is based on a combination of the sweep line paradigm with a novel wavelet function tailored to detect isotopic patterns. We evaluate our technique on several data sets of varying complexity and show that we are able to rapidly quantify peptides with high accuracy in a sound algorithmic framework. |
BibTeX:
@inproceedings{SchulzTrieglaff_PepQuant06,
author = {Ole Schulz-Trieglaff and Rene Hussong and Clemens Gröpl and Andreas Hildebrandt and Knut Reinert},
title = {A Fast and Accurate Algorithm for the Quantification of Peptides from Mass Spectrometry data},
booktitle = {Proceedings of the Eleventh Annual International Conference on Research in Computational Molecular Biology (RECOMB 2007)},
year = {2007},
pages = {473-487}
}
|
| Gröpl, C. & Reinert, K. (2006), "Bioinformatik - Ein ideales Fach, um mathematisch-naturwissenschaftliche Fächer (Biologie, Chemie, Mathematik) mit der Informatik zu verbinden", Talk given at 5. Berliner MNU-Kongress, TU Berlin, http://www.mnu-berlin.de/. |
BibTeX:
@misc{GroRei-MNU06,
author = {Clemens Gröpl and Knut Reinert},
title = {Bioinformatik - Ein ideales Fach, um mathematisch-naturwissenschaftliche Fächer (Biologie, Chemie, Mathematik) mit der Informatik zu verbinden},
howpublished = {Talk given at 5. Berliner MNU-Kongress, TU Berlin, http://www.mnu-berlin.de/},
year = {2006},
url = {http://www.mnu-berlin.de/}
}
|
| Kohlbacher, O., Reinert, K., Gröpl, C., Lange, E., Pfeiffer, N., Schulz-Trieglaff, O. & Sturm, M. (2006), "TOPP - The OpenMS Proteomics Pipeline", In Proceedings of the 5th European Conference on Computational Biology (ECCB 2006). |
| Abstract: Motivation: Experimental techniques in proteomics have seen rapid development over the last few years. Volume and complexity of the data have both been growing at a similar rate. Accordingly, data management and analysis are one of the major challenges in proteomics. Flexible algorithms are required to handle changing experimental setups and to assist in developing and validating new methods. In order to facilitate these studies, it would be desirable to have a flexible `toolbox' of versatile and user-friendly applications allowing for rapid construction of computational workflows in proteomics. Results: We describe a set of tools for proteomics data analysis -- TOPP, The OpenMS Proteomics Pipeline. TOPP provides a set of computational tools which can be easily combined into analysis pipelines even by non-experts and can be used in proteomics workflows. These applications range from useful utilities (file format conversion, peak picking) over wrapper applications for known applications (e.g. Mascot) to completely new algorithmic techniques for data reduction and data analysis. We anticipate that TOPP will greatly facilitate rapid prototyping of proteomics data evaluation pipelines. As such, we describe the basic concepts and the current abilities of TOPP and illustrate these concepts in the context of two example applications: the identification of peptides from a raw data set through database search and the complex analysis of a standard addition experiment for the absolute quantitation of biomarkers. The latter example demonstrates TOPP's ability to construct flexible analysis pipelines in support of complex experimental setups. Availability: The TOPP components are available as open-source software under the lesser GNU public license (LGPL). Source code is available from the project web site at www.OpenMS.de |
BibTeX:
@inproceedings{KRGLPTS06,
author = {Oliver Kohlbacher and Knut Reinert and Clemens Gröpl and Eva Lange and Nico Pfeiffer and Ole Schulz-Trieglaff and Marc Sturm},
title = {TOPP - The OpenMS Proteomics Pipeline},
booktitle = {Proceedings of the 5th European Conference on Computational Biology (ECCB 2006)},
year = {2006}
}
|
| Lange, E., Gröpl, C., Reinert, K., Kohlbacher, O. & Hildebrandt, A. (2006), "High Accuracy Peak-Picking of Proteomics Data using Wavelet Techniques", In Proceedings of the 11th Pacific Symposium on Biocomputing (PSB06)., pp. 243-254. |
| Abstract: A new peak picking algorithm for the analysis of mass spectrometric (MS) data is presented. It is independent of the underlying machine or ionization method, and is able to resolve highly convoluted and asymmetric signals. The method uses the multiscale nature of spectrometric data by first detecting the mass peaks in the wavelet-transformed signal before a given asymmetric peak function is fitted to the raw data. In an optional third stage, the resulting fit can be further improved using techniques from nonlinear optimization. In contrast to currently established techniques (e.g. SNAP, Apex) our algorithm is able to separate overlapping peaks of multiply charged peptides in ESI-MS data of low resolution. Its improved accuracy with respect to peak positions makes it a valuable preprocessing method for MS-based identification and quantification experiments. The method has been validated on a number of different annotated test cases, where it compares favorably in both runtime and accuracy with currently established techniques. An implementation of the algorithm is freely available in our open source framework OpenMS. |
BibTeX:
@inproceedings{LanGroRei06,
author = {Eva Lange and Clemens Gröpl and Knut Reinert and Oliver Kohlbacher and Andreas Hildebrandt},
title = {High Accuracy Peak-Picking of Proteomics Data using Wavelet Techniques},
booktitle = {Proceedings of the 11th Pacific Symposium on Biocomputing (PSB06)},
year = {2006},
pages = {243-254}
}
|
| Mayr, B., Kohlbacher, O., Reinert, K., Sturm, M., Gröpl, C., Lange, E., Klein, C. & Huber, C. (2006), "Absolute Myoglobin Quantitation in Serum by Combining Two-Dimensional Liquid Chromatography-Electrospray Ionization Mass Spectrometry and Novel Data Analysis Algorithms", Journal of Proteome Research. Vol. 5, pp. 414-421. |
| Abstract: To measure myoglobin, a marker for myocardial infarction, directly in human serum, two-dimensional liquid chromatography in combination with electrospray ionization mass spectrometry was applied as an analytical method. High-abundant serum proteins were depleted by strong anion-exchange chromatography. The myoglobin fraction was digested and injected onto a 60 mm x 0.2 mm i.d. monolithic capillary column for quantitation of selected peptides upon mass spectrometric detection. The addition of known amounts of myoglobin to the serum sample was utilized for calibration, and horse myoglobin was added as an internal standard to improve reproducibility. Calibration graphs were linear and facilitated the reproducible and accurate determination of the myoglobin amount present in serum. Manual data evaluation using integrated peak areas and an automated multistage algorithm fitting two-dimensional models of peptide elution profiles and isotope patterns to the mass spectrometric raw data were compared. When the automated method was applied, a myoglobin concentration of 460 pg/íL serum was determined with a maximum relative deviation from the theoretical value of 10.1% and a maximum relative standard deviation of 13.4%. |
BibTeX:
@article{MayKohRei06,
author = {Bettina Mayr and Oliver Kohlbacher and Knut Reinert and Marc Sturm and Clemens Gröpl and Eva Lange and Christoph Klein and Christian Huber},
title = {Absolute Myoglobin Quantitation in Serum by Combining Two-Dimensional Liquid Chromatography-Electrospray Ionization Mass Spectrometry and Novel Data Analysis Algorithms},
journal = {Journal of Proteome Research},
year = {2006},
volume = {5},
pages = {414-421}
}
|
| Schulz-Trieglaff, O., Gröpl, C., Thiemann, J., Reinert, K. & Schlüter, H. (2006), "Peptide Biomarker Discovery for the Diagnosis of Renal Allograft Rejection", Poster presented at the European Conference on Computational Biology (ECCB 2006), Eilat, Israel, http://www.eccb06.org/. |
BibTeX:
@misc{BiomarkerECCB2006,
author = {Ole Schulz-Trieglaff and Clemens Gröpl and Joachim Thiemann and Knut Reinert and Hartmut Schlüter},
title = {Peptide Biomarker Discovery for the Diagnosis of Renal Allograft Rejection},
howpublished = {Poster presented at the European Conference on Computational Biology (ECCB 2006), Eilat, Israel, http://www.eccb06.org/},
year = {2006}
}
|
| Schulz-Trieglaff, O., Gröpl, C., Thiemann, J., Reinert, K. & Schlüter, H. (2006), "Peptide Quantification for the Early Diagnosis of Renal Allograft Rejection", Poster presented at the German Conference on Bioinformatics (GCB 2006), T{\"u}bingen, Germany, http://www.gcb2006.de/. |
BibTeX:
@misc{PepQuant_GCB06,
author = {Ole Schulz-Trieglaff and Clemens Gröpl and Joachim Thiemann and Knut Reinert and Hartmut Schlüter},
title = {Peptide Quantification for the Early Diagnosis of Renal Allograft Rejection},
howpublished = {Poster presented at the German Conference on Bioinformatics (GCB 2006), T{\"u}bingen, Germany, http://www.gcb2006.de/},
year = {2006}
}
|
| Bodirsky, M., Gröpl, C., Johannsen, D. & Kang, M. (2005), "A direct decomposition of 3-connected planar graphs", In Proceedings of the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05). Taormina. |
| Abstract: ABSTRACT. We present a decomposition strategy for c-nets, i. e., rooted 3-connected planar maps. The decomposition yields an algebraic equation for the number of c-nets with a given number of vertices and a given size of the outer face. The decomposition also leads to a deterministic and polynomial time algorithm to sample c-nets uniformly at random. Using rejection sampling, we can also sample isomorphism types of convex polyhedra, i.e., 3-connected planar graphs, uniformly at random. R´E SUM´E. Nous proposons une strat´egie de d´ecomposition pour les cartes point´ees 3-connexes (c-r´eseaux). Cette d´ecomposition permet d’obtenir une ´equation alg´ebrique pour le nombre de c-r´eseaux suivant le nombre de sommets et la taille de la face ext`erieure. On en d´eduit un algorithme de complexit´e en temps polynomiale pour le tirage al´eatoire uniforme des c-r´eseaux. En utilisant une m´ethode `a rejet, nous obtenons aussi un algorithme de tirage al´eatoire uniforme pour les graphes planaires 3-connexes. |
BibTeX:
@inproceedings{BGJK04a,
author = {Manuel Bodirsky and Clemens Gröpl and Daniel Johannsen and Mihyun Kang},
title = {A direct decomposition of 3-connected planar graphs},
booktitle = {Proceedings of the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05)},
year = {2005}
}
|
| Bodirsky, M., Gröpl, C. & Kang, M. (2005), "Sampling Unlabeled Biconnected Planar Graphs", In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05). |
BibTeX:
@inproceedings{BGK05a,
author = {Manuel Bodirsky and Clemens Gröpl and Mihyun Kang},
title = {Sampling Unlabeled Biconnected Planar Graphs},
booktitle = {Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05)},
year = {2005}
}
|
| Gröpl, C. (2005), "An Algorithm for Feature Finding in LC/MS Raw Data", In Computational Proteomics. Dagstuhl Online Publication Server (DROPS). |
BibTeX:
@inproceedings{GroeplFeaFiDagstuhl05,
author = {Clemens Gröpl},
title = {An Algorithm for Feature Finding in LC/MS Raw Data},
booktitle = {Computational Proteomics},
publisher = {Dagstuhl Online Publication Server (DROPS)},
year = {2005},
note = {Extended abstract for talk given at Dagstuhl Seminar 05471 on Computational Proteomics, 20.-25. November 2005},
url = {http://www.dagstuhl.de/05471/}
}
|
| Gröpl, C., Hildebrandt, A., Kohlbacher, O., Lange, E., Lövenich, S. & Sturm, M. (2005), "OpenMS - Software for Mass Spectrometry", Poster presented at the MBI Workshop on Computational Proteomics and Mass Spectrometry, January 11-14, Mathematical Biosciences Institute, Ohio State University, Columbus, Ohio. |
BibTeX:
@misc{OpenMSPosterMBI05,
author = {Clemens Gröpl and Andreas Hildebrandt and Oliver Kohlbacher and Eva Lange and Sandra Lövenich and Marc Sturm},
title = {OpenMS - Software for Mass Spectrometry},
howpublished = {Poster presented at the MBI Workshop on Computational Proteomics and Mass Spectrometry, January 11-14, Mathematical Biosciences Institute, Ohio State University, Columbus, Ohio},
year = {2005},
note = {http://mbi.osu.edu/2004/workshops2004.html}
}
|
| Gröpl, C., Hildebrandt, A., Kohlbacher, O., Lange, E. & Sturm, M. (2005), "OpenMS - a generic open source framework for HPLC/MS-based proteomics", Poster presented at the Fourth Annual World Congress of the Human Proteome Organization, Munich. |
BibTeX:
@misc{OpenMSPosterHUPOMuenchen05,
author = {Clemens Gröpl and Andreas Hildebrandt and Oliver Kohlbacher and Eva Lange and Marc Sturm},
title = {OpenMS - a generic open source framework for HPLC/MS-based proteomics},
howpublished = {Poster presented at the Fourth Annual World Congress of the Human Proteome Organization, Munich},
year = {2005},
note = {http://www.hupo2005.com/}
}
|
| Gröpl, C., Lange, E., Reinert, K., Kohlbacher, O., Sturm, M., Huber, C.G., Mayr, B.M. & Klein, C.L. (2005), "Absolute quantification of the myoglobin content in blood serum using HPLC/MS through automatic bioinformatics analysis", Poster presented at the Fourth Annual World Congress of the Human Proteome Organization (HUPO05), Munich . |
BibTeX:
@misc{AbsQuantMyoPosterHUPOMuenchen05,
author = {Clemens Gröpl and Eva Lange and Knut Reinert and Oliver Kohlbacher and Marc Sturm and Christian G. Huber and Bettina M. Mayr and Christoph L. Klein},
title = {Absolute quantification of the myoglobin content in blood serum using HPLC/MS through automatic bioinformatics analysis},
howpublished = {Poster presented at the Fourth Annual World Congress of the Human Proteome Organization (HUPO05), Munich },
year = {2005},
note = {http://www.hupo2005.com/}
}
|
| Gröpl, C., Lange, E., Reinert, K., Kohlbacher, O., Sturm, M., Huber, C.G., Mayr, B.M. & Klein, C.L. (2005), "Algorithms for the automated absolute quantification of diagnostic markers in complex proteomics samples", In Proceedings of the 1st International Symposium on Computational Life Science (CompLife05)., pp. 151-163. |
| Abstract: HPLC-ESI-MS is rapidly becoming an established standard method for shotgun proteomics. Currently, its major drawbacks are twofold: quantification is mostly limited to relative quantification and the large amount of data produced by every individual experiment can make manual analysis quite difficult. Here we present a new, combined experimental and algorithmic approach to absolutely quantify proteins from samples with unprecedented precision. We apply the method to the analysis of myoglobin in human blood serum, which is an important diagnostic marker for myocardial infarction. Our approach was able to determine the absolute amount of myoglobin in a serum sample through a series of standard addition experiments with a relative error of 2.5 percent. Compared to a manual analysis of the same dataset we could improve the precision and conduct it in a fraction of the time needed for the manual analysis. We anticipate that our automatic quantitation method will facilitate further absolute or relative quantitation of even more complex peptide samples. The algorithm was developed using our publically available software framework OpenMS (www.openms.de). |
BibTeX:
@inproceedings{GLRKSHMK05,
author = {Clemens Gröpl and Eva Lange and Knut Reinert and Oliver Kohlbacher and Marc Sturm and Christian G. Huber and Bettina M. Mayr and Christoph L. Klein},
title = {Algorithms for the automated absolute quantification of diagnostic markers in complex proteomics samples},
booktitle = {Proceedings of the 1st International Symposium on Computational Life Science (CompLife05)},
year = {2005},
pages = {151-163}
}
|
| Lange, E., Gröpl, C., Reinert, K., Kohlbacher, O. & Hildebrandt, A. (2005), "High-accuracy peak picking of proteomics data", In Computational Proteomics. Dagstuhl Online Publication Server (DROPS). |
BibTeX:
@inproceedings{LangePePiDagstuhl05,
author = {Eva Lange and Clemens Gröpl and Knut Reinert and Oliver Kohlbacher and Andreas Hildebrandt},
title = {High-accuracy peak picking of proteomics data},
booktitle = {Computational Proteomics},
publisher = {Dagstuhl Online Publication Server (DROPS)},
year = {2005},
note = {Extended abstract for talk given at Dagstuhl Seminar 05471 on Computational Proteomics, 20.-25. November 2005}
}
|
| Reinert, K., Kohlbacher, O., Gröpl, C., Lange, E., Schulz-Trieglaff, O., Sturm, M. & Pfeifer, N. (2005), "OpenMS - A Framework for Quantitative HPLC/MS-Based Proteomics", In Computational Proteomics. Dagstuhl Online Publication Server (DROPS). |
BibTeX:
@inproceedings{ReinertOpenMSDagstuhl05,
author = {Knut Reinert and Oliver Kohlbacher and Clemens Gröpl and Eva Lange and Ole Schulz-Trieglaff and Marc Sturm and Nico Pfeifer},
title = {OpenMS - A Framework for Quantitative HPLC/MS-Based Proteomics},
booktitle = {Computational Proteomics},
publisher = {Dagstuhl Online Publication Server (DROPS)},
year = {2005},
note = {Extended abstract for talk given at Dagstuhl Seminar 05471 on Computational Proteomics, 20.-25. November 2005}
}
|
| Gröpl, C., Prömel, H. Jü. & Srivastav, A. (2004), "Ordered binary decision diagrams and the Shannon effect", Discrete Applied Mathematics. Vol. 142, pp. 67-85. |
| Abstract: We investigate the size and structure of ordered binary decision diagrams (OBDDs) for random Boolean functions. It was known that for most values of n, the expected OBDD size of a random Boolean function with n variables is equal to the worst-case size up to terms of lower order. Such a phenomenon is generally called strong Shannon effect. Here we show that the strong Shannon effect is not valid for all n. Instead it undergoes a certain periodic `phase transition': If n lies within intervals of constant width around the values n = 2h + h, then the strong Shannon effect does not hold, whereas it does hold outside these intervals. Our analysis provides doubly exponential probability bounds and generalises to ordered Kronecker functional decision diagrams (OKFDDs). |
BibTeX:
@article{GPS04,
author = {Clemens Gröpl and Hans Jürgen Prömel and Anand Srivastav},
title = {Ordered binary decision diagrams and the Shannon effect},
journal = {Discrete Applied Mathematics},
year = {2004},
volume = {142},
pages = {67-85}
}
|
| Bodirsky, M., Gröpl, C. & Kang, M. (2003), "Decomposing, Counting, and Generating Unlabeled Cubic Planar Graphs", In European Conference on Combinatorics, Graph Theory, and Applications EUROCOMB'03 Prague. |
| Abstract: We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for counting the exact number of rooted cubic planar graphs. This leads to 3-connected planar graphs, which have a unique embedding on the sphere; but special care has to be taken for rooted graphs that have a sense-reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted graphs with given symmetries. Colored networks can again be decomposed along their connectivity structure. For rooted 3-connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. All these numbers can be evaluated in polynomial time by dynamic programming. We can use them to generate rooted cubic planar graphs uniformly at random. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm. |
BibTeX:
@inproceedings{BGK03c,
author = {Manuel Bodirsky and Clemens Gröpl and Mihyun Kang},
title = {Decomposing, Counting, and Generating Unlabeled Cubic Planar Graphs},
booktitle = {European Conference on Combinatorics, Graph Theory, and Applications EUROCOMB'03 Prague},
year = {2003}
}
|
| Bodirsky, M., Gröpl, C. & Kang, M. (2003), "Generating labeled planar graphs uniformly at random", In Proceedings of ICALP 2003.(2719), pp. 1095-1107. Springer Verlag. |
| Abstract: We present an expected polynomial time algorithm to generate a labeled planar graph uniformly at random. To generate the planar graphs, we derive recurrence formulas that count all such graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. For 3-connected graphs we apply a recent random generation algorithm by Schaeffer and a counting formula by Mullin and Schellenberg. |
BibTeX:
@inproceedings{BGK03b,
author = {Manuel Bodirsky and Clemens Gröpl and Mihyun Kang},
title = {Generating labeled planar graphs uniformly at random},
booktitle = {Proceedings of ICALP 2003},
publisher = {Springer Verlag},
year = {2003},
number = {2719},
pages = {1095--1107},
note = {Appeared 2008 in Theoretical Computer Science. The download is the journal submission |
| Frömmel, C., Gille, C., Goede, A., Gröpl, C., Hougardy, S., Nierhoff, T., Preissner, R. & Thimm, M. (2003), "Accelerating screening of 3D protein data with a graph theoretical approach", Bioinformatics., December, 2003. Vol. 19(18), pp. 2442-2447. |
| Abstract: Motivation: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches. Results: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search. 10.1093/bioinformatics/btg343 |
BibTeX:
@article{FGGGHNPT03,
author = {Frömmel, Cornelius and Gille, Christoph and Goede, Andrean and Gröpl, Clemens and Hougardy, Stefan and Nierhoff, Till and Preissner, Robert and Thimm, Martin },
title = {Accelerating screening of 3D protein data with a graph theoretical approach},
journal = {Bioinformatics},
year = {2003},
volume = {19},
number = {18},
pages = {2442--2447},
url = {http://dx.doi.org/10.1093/bioinformatics/btg343},
doi = {http://dx.doi.org/10.1093/bioinformatics/btg343}
}
|
| Frömmel, C., Gille, C., Goede, A., Gröpl, C., Hougardy, S., Nierhoff, T., Preißner, R. & Thimm, M. (2003), "Accelerating screening of 3D protein data with a graph theoretical approach", Bioinformatics. Vol. 19, pp. 2442-2447. |
| Abstract: Motivation: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches. Results: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search. |
BibTeX:
@article{FGGGHNPT03_prelim,
author = {C. Frömmel and C. Gille and A. Goede and C. Gröpl and S. Hougardy and T. Nierhoff and R. Preißner and M. Thimm},
title = {Accelerating screening of 3D protein data with a graph theoretical approach},
journal = {Bioinformatics},
year = {2003},
volume = {19},
pages = {2442-2447},
note = {Please note that this downloadable version is a preliminary version that differs from the final published version},
url = {http://bioinformatics.oupjournals.org}
}
|
| Frömmel, C., Gille, C., Goede, A., Gröpl, C., Hougardy, S., Nierhoff, T., Preißner, R. & Thimm, M. (2003), "Accelerating Screening of 3D Protein Data with a Graph Theoretical Approach". |
BibTeX:
@misc{FGGGHNPT03b,
author = {C. Frömmel and C. Gille and A. Goede and C. Gröpl and S. Hougardy and T. Nierhoff and R. Preißner and M. Thimm},
title = {Accelerating Screening of 3D Protein Data with a Graph Theoretical Approach},
year = {2003},
note = {Poster presented at RECOMB 2003}
}
|
| Gröpl, C. (2003), "Algorithmen in der Bioinformatik". |
| Abstract: Skript zu meiner Vorlesung über "Algorithmen in der Bioinformatik" im Wintersemester 2002/03 am Institut für Informatik der Humboldt-Universität zu Berlin |
BibTeX:
@misc{GroeplAlgBio2002,
author = {Clemens Gröpl},
title = {Algorithmen in der Bioinformatik},
year = {2003},
note = {Skript zu meiner Vorlesung im Wintersemester 2002/03 am Institut für Informatik der Humboldt-Universität zu Berlin}
}
|
| Gröpl, C., Hougardy, S., Nierhoff, T. & Prömel, H. Jü. (2002), "Steiner trees in uniformly quasi-bipartite graphs", Information Processing Letters. Vol. 83, pp. 195-200. |
| Abstract: The area of approximation algorithms for the Steiner tree problem in graphs has seen continuous progress over the last years. Currently the best approximation algorithm has a performance ratio of 1.550. This is still far away from 1.0074, the largest known lower bound on the achievable performance ratio. As all instances resulting from known lower bound reductions are uniformly quasi-bipartite, it is interesting whether this special case can be approximated better than the general case. We present an approximation algorithm with performance ratio 73/60 < 1.217 for the uniformly quasi-bipartite case. This improves on the previously known ratio of 1.279 of Robins and Zelikovsky. We use a new method of analysis that combines ideas from the greedy algorithm for set cover with a matroid-style exchange argument to model the connectivity constraint. As a consequence, we are able to provide a tight instance. |
BibTeX:
@article{GHNP01d,
author = {Clemens Gröpl and Stefan Hougardy and Till Nierhoff and Hans Jürgen Prömel},
title = {Steiner trees in uniformly quasi-bipartite graphs},
journal = {Information Processing Letters},
year = {2002},
volume = {83},
pages = {195-200}
}
|
| Gröpl, C., Hougardy, S., Nierhoff, T., Prömel, H. Jü. & Thimm, M. (2002), "Approximationsalgorithmen für das Steinerbaumproblem in Graphen", Poster. |
BibTeX:
@misc{Steinerbaum-Poster,
author = {Clemens Gröpl and Stefan Hougardy and Till Nierhoff and Hans Jürgen Prömel and Martin Thimm},
title = {Approximationsalgorithmen für das Steinerbaumproblem in Graphen},
howpublished = {Poster},
year = {2002}
}
|
| Gröpl, C., Hougardy, S., Nierhoff, T. & Prömel, H. Jü. (2001), "Approximation Algorithms for the Steiner Tree Problem in Graphs", In Steiner Trees in Industry. , pp. 235-279. Kluwer Academic Publishers. |
BibTeX:
@incollection{GHNP01a,
author = {Clemens Gröpl and Stefan Hougardy and Till Nierhoff and Hans Jürgen Prömel},
title = {Approximation Algorithms for the Steiner Tree Problem in Graphs},
booktitle = {Steiner Trees in Industry},
publisher = {Kluwer Academic Publishers},
year = {2001},
pages = {235-279},
note = {Survey article with new proofs}
}
|
| Gröpl, C., Hougardy, S., Nierhoff, T. & Prömel, H. Jü. (2001), "Lower bounds for approximation algorithms for the Steiner tree problem", In Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (2001). Springer Verlag. |
| Abstract: The Steiner tree problem asks for a shortest subgraph connecting a given set of terminals in a graph. It is known to be APX-complete, which means that no polynomial time approximation scheme can exist for this problem, unless P=NP. Currently, the best approximation algorithm for the Steiner tree problem has a performance ratio of $1.55$, whereas the corresponding lower bound is smaller than $1.01$. In this paper, we provide for several Steiner tree approximation algorithms lower bounds on their performance ratio that are much larger. For two algorithms that solve the Steiner tree problem on quasi-bipartite instances, we even prove lower bounds that match the upper bounds. Quasi-bipartite instances are of special interest, as currently all known lower bound reductions for the Steiner tree problem in graphs produce such instances. |
BibTeX:
@inproceedings{GHNP01b,
author = {Clemens Gröpl and Stefan Hougardy and Till Nierhoff and Hans Jürgen Prömel},
title = {Lower bounds for approximation algorithms for the Steiner tree problem},
booktitle = {Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (2001)},
publisher = {Springer Verlag},
year = {2001}
}
|
| Gröpl, C., Prömel, H. Jü. & Srivastav, A. (2001), "On the Evolution of the Worst-Case OBDD Size", Information Processing Letters. Vol. 77, pp. 1-7. |
| Abstract: We prove matching lower and upper bounds on the worst-case OBDD size of a Boolean function, revealing an interesting ocillating behaviour. |
BibTeX:
@article{GPS01,
author = {Clemens Gröpl and Hans Jürgen Prömel and Anand Srivastav},
title = {On the Evolution of the Worst-Case OBDD Size},
journal = {Information Processing Letters},
year = {2001},
volume = {77},
pages = {1-7}
}
|
| Baudis, G., Gröpl, C., Hougardy, S., Nierhoff, T. & Prömel, H. Jü. (2000), "Approximating Minimum Spanning Sets in Hypergraphs and Polymatroids". Humboldt-University Berlin, 2000. |
| Abstract: We present a new analysis of the greedy algorithm for the problem of finding a minimum spanning subset in k-polymatroids. This algorithm has a performance ratio of approximately ln k, which is best possible for large k. A consequence of this algorithm is a polynomial time approximation algorithm with approximation ratio ln k for finding minimum weight spanning subhypergraphs in (k+1)-restricted hypergraphs. This generalization of the well-known set cover problem naturally arises when computing Steiner minimum trees. Other applications of the algorithm include the rigidity problem in statics. |
BibTeX:
@techreport{BGHNP00,
author = {Gregor Baudis and Clemens Gröpl and Stefan Hougardy and Till Nierhoff and Hans Jürgen Prömel},
title = {Approximating Minimum Spanning Sets in Hypergraphs and Polymatroids},
year = {2000},
note = {This paper was already accepted for ICALP 2000 but we did not present it since later we were informed that the main result had already been proven in a different way.}
}
|
| Gröpl, C. (1999), "Binary Decision Diagrams for Random Boolean Functions". School: Humboldt-Universität zu Berlin. |
| Abstract: (deutsche Zusammenfassung siehe unten) Binary Decision Diagrams (BDDs) are a data structure for Boolean functions which are also known as branching programs. In ordered binary decision diagrams (OBDDs), the tests have to obey a fixed variable ordering. In free binary decision diagrams (FBDDs), each variable can be tested at most once. The efficiency of new variants of the BDD concept is usually demonstrated with spectacular (worst-case) examples. We pursue another approach and compare the representation sizes of almost all Boolean functions. Whereas I. Wegener proved that for `most' values of n the expected OBDD size of a random Boolean function of n variables is equal to the worst-case size up to terms of lower order, we show that this is not the case for n within intervals of constant length around the values n = 2h + h. Furthermore, ranges of n exist for which minimal FBDDs are almost always at least a constant factor smaller than minimal OBDDs. Our main theorems have doubly exponentially small probability bounds (in n). We also investigate the evolution of random OBDDs and their worst-case size, revealing an oscillating behaviour that explains why certain results cannot be improved in general. Zusammenfassung: Binary Decision Diagrams (BDDs) sind eine Datenstruktur für Boolesche Funktionen, die auch unter dem Namen branching program bekannt ist. In ordered binary decision diagrams (OBDDs) müssen die Tests einer festen Variablenordnung genügen. In free binary decision diagrams (FBDDs) darf jede Variable höchstens einmal getestet werden. Die Effizienz neuer Varianten des BDD-Konzepts wird gewöhnlich anhand spektakulärer (worst-case) Beispiele aufgezeigt. Wir verfolgen einen anderen Ansatz und vergleichen die Darstellungsgrößen für fast alle Booleschen Funktionen. Während I. Wegener bewiesen hat, daß für die `meisten' n die erwartete OBDD-Größe einer zufälligen Booleschen Funktion von n Variablen gleich der worst-case Größe bis auf Terme kleinerer Ordnung ist, zeigen wir daß dies nicht der Fall ist für n innerhalb von Intervallen konstanter Länge um die Werte n = 2h + h. Ferner gibt es Bereiche von n, in denen minimale FBDDs fast immer um mindestens einen konstanten Faktor kleiner sind als minimale OBDDs. Unsere Hauptsätze ha ben doppelt exponentielle Wahrschein- lichkeitsschranken (in n). Außerdem untersuchen wir die Entwicklung zufälliger OBDDs und ihrer worst-case Größe und decken dabei ein oszillierendes Verhalten auf, das erklärt, warum gewisse Aussagen im allgemeinen nicht verstärkt werden können. Schlagwörter: Binäres Entscheidungsdiagramm, Boolesche Funktion,probabilistische Analyse, Shannon Effekt. |
BibTeX:
@phdthesis{Groepl99,
author = {Clemens Gröpl},
title = {Binary Decision Diagrams for Random Boolean Functions},
school = {Humboldt-Universität zu Berlin},
year = {1999},
url = {http://dochost.rz.hu-berlin.de/dissertationen/informatik/groepl-clemens}
}
|
| Gröpl, C., Prömel, H. Jü. & Srivastav, A. (1998), "Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract)", In STACS 98. Berlin, Heidelberg, New York.(1373), pp. 238-248. Springer Verlag. |
| Abstract: We investigate the size and structure of ordered binary decision diagrams (OBDDs) for random Boolean functions.Wegener [Weg94] proved that for “most” values of n, the expected OBDD-size of a random Boolean function with n variables equals the worst-case size up to terms of lower order. Our main result is that this phenomenon, also known as strong Shannon effect, shows a threshold behaviour: The strong Shannon effect does not hold within intervals of constant width around the values n=2^h+2, but it does hold outside these intervals. Also, the oscillation of the expected and the worst-case size is described. Methodical innovations of our approach are a functional equation to locate “critical levels” in OBDDs and the use of Azuma’s martingale inequality and Chv´atal’s large deviation inequality for the hypergeometric distribution. This leads to significant improvements over Wegener’s probability bounds. |
BibTeX:
@inproceedings{GPS98,
author = {Clemens Gröpl and Hans Jürgen Prömel and Anand Srivastav},
title = {Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract)},
booktitle = {STACS 98},
publisher = {Springer Verlag},
year = {1998},
number = {1373},
pages = {238--248}
}
|
| Gröpl, C. & Skutella, M. (1998), "Parallel Repetition of MIP(2,1) Systems", In Lectures on Proof Verification and Approximation Algorithms. Vol. 1367, pp. 161-177. Springer. |
BibTeX:
@incollection{GS98,
author = {Clemens Gröpl and Martin Skutella},
title = {Parallel Repetition of MIP(2,1) Systems},
booktitle = {Lectures on Proof Verification and Approximation Algorithms},
publisher = {Springer},
year = {1998},
volume = {1367},
pages = {161-177},
note = {The book grow out of a Dagstuhl Seminar, April 21-25, 1997}
}
|
| Block, M., Gröpl, C., Preuss, H., Prömel, H. Jü. & Srivastav, A. (1997), "Efficient ordering of state variables and transition relation partitions in symbolic model checking". Humboldt-Universität zu Berlin, 1997. |
| Abstract: Among the main algorithmic problems in the verification of sequential circuits are the computation of good orders of state variables and transition relation partitions. Existing model checking packages like SMV from CMU, VIS from Berkeley or Rulebase from IBM Haifa provide variants of Rudell's sifting algorithm for the variable ordering problem and greedy-type algorithms for the partition ordering problem. For both problems, we give new simulated annealing based algorithms and we provide a model checking program called VERIFY which is based on SMV. The impact of our approach is demonstrated on industrial arbiter circuits and ISCAS '89 benchmarks. In particular on large industrial circuits our algorithms show a better space/time performance than previously given heuristics. |
BibTeX:
@techreport{BGPPS97,
author = {Mathias Block and Clemens Gröpl and Harry Preuss and Hans Jürgen Prömel and Anand Srivastav},
title = {Efficient ordering of state variables and transition relation partitions in symbolic model checking},
year = {1997}
}
|
| Gröpl, C. (1996), "Über Approximationsalgorithmen zur Färbung $k$-färbbarer Graphen, die vektorchromatische Zahl und andere Varianten der $vartheta$-Funktion". School: Rheinische Friedrich-Wilhelms-Universität Bonn. Forschungsinstitut für Diskrete Mathematik, January, 1996. |
BibTeX:
@mastersthesis{Groepl96,
author = {Clemens Gröpl},
title = {Über Approximationsalgorithmen zur Färbung $k$-färbbarer Graphen, die vektorchromatische Zahl und andere Varianten der $vartheta$-Funktion},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = {1996}
}
|
Created by JabRef on 29/05/2009 using a modified version of Mark Schenk's "List of References" export filter