56 Search Results for "Schultz, R�diger"


Document
Design and Analysis of a Logless Dynamic Reconfiguration Protocol

Authors: William Schultz, Siyuan Zhou, Ian Dardik, and Stavros Tripakis

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)


Abstract
Distributed replication systems based on the replicated state machine model have become ubiquitous as the foundation of modern database systems. To ensure availability in the presence of faults, these systems must be able to dynamically replace failed nodes with healthy ones via dynamic reconfiguration. MongoDB is a document oriented database with a distributed replication mechanism derived from the Raft protocol. In this paper, we present MongoRaftReconfig, a novel dynamic reconfiguration protocol for the MongoDB replication system. MongoRaftReconfig utilizes a logless approach to managing configuration state and decouples the processing of configuration changes from the main database operation log. The protocol’s design was influenced by engineering constraints faced when attempting to redesign an unsafe, legacy reconfiguration mechanism that existed previously in MongoDB. We provide a safety proof of MongoRaftReconfig, along with a formal specification in TLA+. To our knowledge, this is the first published safety proof and formal specification of a reconfiguration protocol for a Raft-based system. We also present results from model checking the safety properties of MongoRaftReconfig on finite protocol instances. Finally, we discuss the conceptual novelties of MongoRaftReconfig, how it can be understood as an optimized and generalized version of the single server reconfiguration algorithm of Raft, and present an experimental evaluation of how its optimizations can provide performance benefits for reconfigurations.

Cite as

William Schultz, Siyuan Zhou, Ian Dardik, and Stavros Tripakis. Design and Analysis of a Logless Dynamic Reconfiguration Protocol. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{schultz_et_al:LIPIcs.OPODIS.2021.26,
  author =	{Schultz, William and Zhou, Siyuan and Dardik, Ian and Tripakis, Stavros},
  title =	{{Design and Analysis of a Logless Dynamic Reconfiguration Protocol}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.26},
  URN =		{urn:nbn:de:0030-drops-158016},
  doi =		{10.4230/LIPIcs.OPODIS.2021.26},
  annote =	{Keywords: Fault Tolerance, Dynamic Reconfiguration, State Machine Replication}
}
Document
Brief Announcement
Brief Announcement: Design and Verification of a Logless Dynamic Reconfiguration Protocol in MongoDB Replication

Authors: William Schultz, Siyuan Zhou, and Stavros Tripakis

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
We introduce a novel dynamic reconfiguration protocol for the MongoDB replication system that extends and generalizes the single server reconfiguration protocol of the Raft consensus algorithm. Our protocol decouples the processing of configuration changes from the main database operation log, which allows reconfigurations to proceed in cases when the main log is prevented from processing new operations. Additionally, this decoupling allows for configuration state to be managed by a logless replicated state machine, storing only the latest version of the configuration and avoiding the complexities of a log-based protocol. We present a formal specification of the protocol in TLA+, initial verification results of model checking its safety properties, and an experimental evaluation of how reconfigurations are able to quickly restore a system to healthy operation when node failures have stalled the main operation log. This announcement is a short version and the full paper is available at [Schultz et al., 2021].

Cite as

William Schultz, Siyuan Zhou, and Stavros Tripakis. Brief Announcement: Design and Verification of a Logless Dynamic Reconfiguration Protocol in MongoDB Replication. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 61:1-61:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{schultz_et_al:LIPIcs.DISC.2021.61,
  author =	{Schultz, William and Zhou, Siyuan and Tripakis, Stavros},
  title =	{{Brief Announcement: Design and Verification of a Logless Dynamic Reconfiguration Protocol in MongoDB Replication}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{61:1--61:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.61},
  URN =		{urn:nbn:de:0030-drops-148636},
  doi =		{10.4230/LIPIcs.DISC.2021.61},
  annote =	{Keywords: Reconfiguration, Consensus, State Machine Replication}
}
Document
Short Paper
lambdaProlog(QS): Functional Spatial Reasoning in Higher Order Logic Programming (Short Paper)

Authors: Beidi Li, Mehul Bhatt, and Carl Schultz

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)


Abstract
We present a framework and proof-of-concept implementation for functional spatial reasoning within high-order logic programming. The developed approach extends lambdaProlog to support reasoning over spatial variables via Constraint Handling Rules. We implement our approach within Embeddable lambdaProlog Interpreter (ELPI) and demonstrate key features from combined reasoning over spatial functions and relations. The reported research is an ongoing development of the declarative spatial reasoning paradigm.

Cite as

Beidi Li, Mehul Bhatt, and Carl Schultz. lambdaProlog(QS): Functional Spatial Reasoning in Higher Order Logic Programming (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 26:1-26:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.COSIT.2019.26,
  author =	{Li, Beidi and Bhatt, Mehul and Schultz, Carl},
  title =	{{lambdaProlog(QS): Functional Spatial Reasoning in Higher Order Logic Programming}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{26:1--26:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.26},
  URN =		{urn:nbn:de:0030-drops-111183},
  doi =		{10.4230/LIPIcs.COSIT.2019.26},
  annote =	{Keywords: Spatial reasoning, Functional logic programming, Lambda-Prolog}
}
Document
Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy (Dagstuhl Seminar 18442)

Authors: Andrea Fuster, Evren Özarslan, Thomas Schultz, and Eugene Zhang

Published in: Dagstuhl Reports, Volume 8, Issue 10 (2019)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18442, "Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy", which was attended by 30 international researchers, both junior and senior. Directional preferences or anisotropies are encountered across many different disciplines and spatial scales. These disciplines share a need for modeling, processing, and visualizing anisotropic quantities, which poses interesting challenges to applied computer science. With the goal of identifying open problems, making practitioners aware of existing solutions, and discovering synergies between different applications in which anisotropy arises, this seminar brought together researchers working on different aspects of computer science with experts from neuroimaging and astronomy. This report gathers abstracts of the talks held by the participants, as well as an account of topics raised within the breakout sessions.

Cite as

Andrea Fuster, Evren Özarslan, Thomas Schultz, and Eugene Zhang. Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy (Dagstuhl Seminar 18442). In Dagstuhl Reports, Volume 8, Issue 10, pp. 148-172, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{fuster_et_al:DagRep.8.10.148,
  author =	{Fuster, Andrea and \"{O}zarslan, Evren and Schultz, Thomas and Zhang, Eugene},
  title =	{{Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy (Dagstuhl Seminar 18442)}},
  pages =	{148--172},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{10},
  editor =	{Fuster, Andrea and \"{O}zarslan, Evren and Schultz, Thomas and Zhang, Eugene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.10.148},
  URN =		{urn:nbn:de:0030-drops-103524},
  doi =		{10.4230/DagRep.8.10.148},
  annote =	{Keywords: Anisotropy, astronomy, diffusion-weighted imaging (DWI), geometry processing, tensor fields, topology, visualization, uncertainty, shape modeling, microstructure imaging, statistical analysis}
}
Document
Geodesic Obstacle Representation of Graphs

Authors: Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin, and Luis Fernando Schultz Xavier da Silveira

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi [Therese C. Biedl and Saeed Mehrabi, 2017] studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the L_1 (Manhattan) shortest paths in the plane that avoid obstacles. In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.

Cite as

Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin, and Luis Fernando Schultz Xavier da Silveira. Geodesic Obstacle Representation of Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.ICALP.2018.23,
  author =	{Bose, Prosenjit and Carmi, Paz and Dujmovic, Vida and Mehrabi, Saeed and Montecchiani, Fabrizio and Morin, Pat and Silveira, Luis Fernando Schultz Xavier da},
  title =	{{Geodesic Obstacle Representation of Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.23},
  URN =		{urn:nbn:de:0030-drops-90274},
  doi =		{10.4230/LIPIcs.ICALP.2018.23},
  annote =	{Keywords: Obstacle representation, Grid obstacle representation, Geodesic obstacle representation}
}
Document
Evidence-Based Parametric Design: Computationally Generated Spatial Morphologies Satisfying Behavioural-Based Design Constraints

Authors: Vasiliki Kondyli, Carl Schultz, and Mehul Bhatt

Published in: LIPIcs, Volume 86, 13th International Conference on Spatial Information Theory (COSIT 2017)


Abstract
Parametric design is an established method in engineering and architecture facilitating the rapid generation and evaluation of a large number of configurations and shapes of complex physical structures according to constraints specified by the designer. However, the emphasis of parametric design systems, particularly in the context of architectural design of large-scale spaces, is on numerical aspects (e.g., maximising areas, specifying dimensions of walls) and does not address human-centred design criteria, for example, as developed from behavioural evidence-based studies. This paper aims at providing an evidence-based human-centred approach for defining design constraints for parametric modelling systems. We determine design rules that address wayfinding issues through behavioural multi-modal data analysis of a wayfinding case study in two healthcare environments of the Parkland hospital (Dallas). Our rules are related to the environmental factors of visibility and positioning of manifest cues along the navigation route. We implement our rules in FreeCAD, an open-source parametric system.

Cite as

Vasiliki Kondyli, Carl Schultz, and Mehul Bhatt. Evidence-Based Parametric Design: Computationally Generated Spatial Morphologies Satisfying Behavioural-Based Design Constraints. In 13th International Conference on Spatial Information Theory (COSIT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 86, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{kondyli_et_al:LIPIcs.COSIT.2017.11,
  author =	{Kondyli, Vasiliki and Schultz, Carl and Bhatt, Mehul},
  title =	{{Evidence-Based Parametric Design: Computationally Generated Spatial Morphologies Satisfying Behavioural-Based Design Constraints}},
  booktitle =	{13th International Conference on Spatial Information Theory (COSIT 2017)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-043-9},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{86},
  editor =	{Clementini, Eliseo and Donnelly, Maureen and Yuan, May and Kray, Christian and Fogliaroni, Paolo and Ballatore, Andrea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2017.11},
  URN =		{urn:nbn:de:0030-drops-77682},
  doi =		{10.4230/LIPIcs.COSIT.2017.11},
  annote =	{Keywords: parametric modelling, behavioural studies, Evidence-Based Design, design computing, wayfinding, spatial cognition}
}
Document
Multidisciplinary Approaches to Multivalued Data: Modeling, Visualization, Analysis (Dagstuhl Seminar 16142)

Authors: Ingrid Hotz, Evren Özarslan, and Thomas Schultz

Published in: Dagstuhl Reports, Volume 6, Issue 4 (2016)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16142, "Multidisciplinary Approaches to Multivalued Data: Modelling, Visualization, Analysis", which was attended by 27 international researchers, both junior and senior. Modelling multivalued data using tensors and higher-order descriptors has become common practice in neuroscience, engineering, and medicine. Novel tools for image analysis, visualization, as well as statistical hypothesis testing and machine learning are required to extract value from such data, and can only be developed within multidisciplinary collaborations. This report gathers abstracts of the talks held by participants on recent advances and open questions related to these challenges, as well as an account of topics raised within two of the breakout sessions.

Cite as

Ingrid Hotz, Evren Özarslan, and Thomas Schultz. Multidisciplinary Approaches to Multivalued Data: Modeling, Visualization, Analysis (Dagstuhl Seminar 16142). In Dagstuhl Reports, Volume 6, Issue 4, pp. 16-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{hotz_et_al:DagRep.6.4.16,
  author =	{Hotz, Ingrid and \"{O}zarslan, Evren and Schultz, Thomas},
  title =	{{Multidisciplinary Approaches to Multivalued Data: Modeling, Visualization, Analysis (Dagstuhl Seminar 16142)}},
  pages =	{16--38},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{4},
  editor =	{Hotz, Ingrid and \"{O}zarslan, Evren and Schultz, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.4.16},
  URN =		{urn:nbn:de:0030-drops-61517},
  doi =		{10.4230/DagRep.6.4.16},
  annote =	{Keywords: visualization, image processing, statistical analysis, machine learning, tensor fields, higher-order descriptors, diffusion-weighted imaging (DWI), structural mechanics, fluid dynamics, microstructure imaging, connectomics, uncertainty visualization, feature extraction}
}
Document
Complete Volume
OASIcs, Volume 34, GCB'13, Complete Volume

Authors: Tim Beißbarth, Martin Kollmar, Andreas Leha, Burkhard Morgenstern, Anne-Kathrin Schultz, Stephan Waack, and Edgar Wingender

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


Abstract
OASIcs, Volume 34, GCB'13, Complete Volume

Cite as

German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Proceedings{beibarth_et_al:OASIcs.GCB.2013,
  title =	{{OASIcs, Volume 34, GCB'13, Complete Volume}},
  booktitle =	{German Conference on Bioinformatics 2013},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013},
  URN =		{urn:nbn:de:0030-drops-42563},
  doi =		{10.4230/OASIcs.GCB.2013},
  annote =	{Keywords: Life and Medical Sciences}
}
Document
Front Matter
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Tim Beißbarth, Martin Kollmar, Andreas Leha, Burkhard Morgenstern, Anne-Kathrin Schultz, Stephan Waack, and Edgar Wingender

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


Abstract
Frontmatter, Table of Contents, Preface, Conference Organization

Cite as

German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. i-xiii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{beibarth_et_al:OASIcs.GCB.2013.i,
  author =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{i--xiii},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.i},
  URN =		{urn:nbn:de:0030-drops-42265},
  doi =		{10.4230/OASIcs.GCB.2013.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
On the estimation of metabolic profiles in metagenomics

Authors: Kathrin Petra Aßhauer and Peter Meinicke

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


Abstract
Metagenomics enables the characterization of the specific metabolic potential of a microbial community. The common approach towards a quantitative representation of this potential is to count the number of metagenomic sequence fragments that can be assigned to metabolic pathways by means of predicted gene functions. The resulting pathway abundances make up the metabolic profile of the metagenome and several different schemes for computing these profiles have been used. So far, none of the existing approaches actually estimates the proportion of sequences that can be assigned to a particular pathway. In most publications of metagenomic studies, the utilized abundance scores lack a clear statistical meaning and usually cannot be compared across different studies. Here, we introduce a mixture model-based approach to the estimation of pathway abundances that provides a basis for statistical interpretation and fast computation of metabolic profiles. Using the KEGG database our results on a large-scale analysis of data from the Human Microbiome Project show a good representation of metabolic differences between different body sites. Further, the results indicate that our mixture model even provides a better representation than the dedicated HUMAnN tool which has been developed for metabolic analysis of human microbiome data.

Cite as

Kathrin Petra Aßhauer and Peter Meinicke. On the estimation of metabolic profiles in metagenomics. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{ahauer_et_al:OASIcs.GCB.2013.1,
  author =	{A{\ss}hauer, Kathrin Petra and Meinicke, Peter},
  title =	{{On the estimation of metabolic profiles in metagenomics}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{1--13},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.1},
  URN =		{urn:nbn:de:0030-drops-42380},
  doi =		{10.4230/OASIcs.GCB.2013.1},
  annote =	{Keywords: metagenomics, metabolic profiling, taxonomic profiling, abundance estimation, mixture modeling}
}
Document
On Weighting Schemes for Gene Order Analysis

Authors: Matthias Bernt, Nicolas Wieseke, and Martin Middendorf

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


Abstract
Gene order analysis aims at extracting phylogenetic information from the comparison of the order and orientation of the genes on the genomes of different species. This can be achieved by computing parsimonious rearrangement scenarios, i.e. to determine a sequence of rearrangements events that transforms one given gene order into another such that the sum of weights of the included rearrangement events is minimal. In this sequence only certain types of rearrangements, given by the rearrangement model, are admissible and weights are assigned with respect to the rearrangement type. The choice of a suitable rearrangement model and corresponding weights for the included rearrangement types is important for the meaningful reconstruction. So far the analysis of weighting schemes for gene order analysis has not been considered sufficiently. In this paper weighting schemes for gene order analysis are considered for two rearrangement models: 1) inversions, transpositions, and inverse transpositions; 2) inversions, block interchanges, and inverse transpositions. For both rearrangement models we determined properties of the weighting functions that exclude certain types of rearrangements from parsimonious rearrangement scenarios.

Cite as

Matthias Bernt, Nicolas Wieseke, and Martin Middendorf. On Weighting Schemes for Gene Order Analysis. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 14-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{bernt_et_al:OASIcs.GCB.2013.14,
  author =	{Bernt, Matthias and Wieseke, Nicolas and Middendorf, Martin},
  title =	{{On Weighting Schemes for Gene Order Analysis}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{14--23},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.14},
  URN =		{urn:nbn:de:0030-drops-42354},
  doi =		{10.4230/OASIcs.GCB.2013.14},
  annote =	{Keywords: Gene order analysis, maximum parsimony, weighting}
}
Document
Alignment-free sequence comparison with spaced k-mers

Authors: Marcus Boden, Martin Schöneich, Sebastian Horwege, Sebastian Lindner, Chris Leimeister, and Burkhard Morgenstern

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


Abstract
Alignment-free methods are increasingly used for genome analysis and phylogeny reconstruction since they circumvent various difficulties of traditional approaches that rely on multiple sequence alignments. In particular, they are much faster than alignment-based methods. Most alignment-free approaches work by analyzing the k-mer composition of sequences. In this paper, we propose to use 'spaced k-mers', i.e. patterns of deterministic and 'don't care' positions instead of contiguous k-mers. Using simulated and real-world sequence data, we demonstrate that this approach produces better phylogenetic trees than alignment-free methods that rely on contiguous k-mers. In addition, distances calculated with spaced k-mers appear to be statistically more stable than distances based on contiguous k-mers.

Cite as

Marcus Boden, Martin Schöneich, Sebastian Horwege, Sebastian Lindner, Chris Leimeister, and Burkhard Morgenstern. Alignment-free sequence comparison with spaced k-mers. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 24-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{boden_et_al:OASIcs.GCB.2013.24,
  author =	{Boden, Marcus and Sch\"{o}neich, Martin and Horwege, Sebastian and Lindner, Sebastian and Leimeister, Chris and Morgenstern, Burkhard},
  title =	{{Alignment-free sequence comparison with spaced k-mers}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{24--34},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.24},
  URN =		{urn:nbn:de:0030-drops-42334},
  doi =		{10.4230/OASIcs.GCB.2013.24},
  annote =	{Keywords: Alignment-free sequence comparison, phylogeny reconstruction}
}
Document
PanCake: A Data Structure for Pangenomes

Authors: Corinna Ernst and Sven Rahmann

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


Abstract
We present a pangenome data structure ("PanCake") for sets of related genomes, based on bundling similar sequence regions into shared features, which are derived from genome-wide pairwise sequence alignments. We discuss the design of the data structure, basic operations on it and methods to predict core genomes and singleton regions. In contrast to many other pangenome analysis tools, like EDGAR or PGAT, PanCake is independent of gene annotations. Nevertheless, comparison of identified core and singleton regions shows good agreements. The PanCake data structure requires significantly less space than the sum of individual sequence files.

Cite as

Corinna Ernst and Sven Rahmann. PanCake: A Data Structure for Pangenomes. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 35-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{ernst_et_al:OASIcs.GCB.2013.35,
  author =	{Ernst, Corinna and Rahmann, Sven},
  title =	{{PanCake: A Data Structure for Pangenomes}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{35--45},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.35},
  URN =		{urn:nbn:de:0030-drops-42314},
  doi =		{10.4230/OASIcs.GCB.2013.35},
  annote =	{Keywords: pangenome, data structure, core genome, comparative genomics}
}
Document
Reconstructing Consensus Bayesian Network Structures with Application to Learning Molecular Interaction Networks

Authors: Holger Fröhlich and Gunnar W. Klau

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


Abstract
Bayesian Networks are an established computational approach for data driven network inference. However, experimental data is limited in its availability and corrupted by noise. This leads to an unavoidable uncertainty about the correct network structure. Thus sampling or bootstrap based strategies are applied to obtain edge frequencies. In a more general sense edge frequencies can also result from integrating networks learned on different datasets or via different inference algorithms. Subsequently one typically wants to derive a biological interpretation from the results in terms of a consensus network. We here propose a log odds based edge score on the basis of the expected false positive rate and thus avoid the selection of a subjective edge frequency cutoff. Computing a score optimal consensus network in our new model amounts to solving the maximum weight acyclic subdigraph problem. We use a branch-and-cut algorithm based on integer linear programming for this task. Our empirical studies on simulated and real data demonstrate a consistently improved network reconstruction accuracy compared to two threshold based strategies.

Cite as

Holger Fröhlich and Gunnar W. Klau. Reconstructing Consensus Bayesian Network Structures with Application to Learning Molecular Interaction Networks. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 46-55, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{frohlich_et_al:OASIcs.GCB.2013.46,
  author =	{Fr\"{o}hlich, Holger and Klau, Gunnar W.},
  title =	{{Reconstructing Consensus Bayesian Network Structures with Application to Learning Molecular Interaction Networks}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{46--55},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.46},
  URN =		{urn:nbn:de:0030-drops-42273},
  doi =		{10.4230/OASIcs.GCB.2013.46},
  annote =	{Keywords: Bayesian Networks, Network Reverse Engineering, Minimum Feedback Arc Set, Maximum Acyclic Subgraph, Molecular Interaction Networks}
}
Document
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-dev.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}
}
  • Refine by Author
  • 3 Beißbarth, Tim
  • 3 Bhatt, Mehul
  • 3 Leha, Andreas
  • 3 Morgenstern, Burkhard
  • 3 Schultz, Carl
  • Show More...

  • Refine by Classification
  • 2 Information systems → Parallel and distributed DBMSs
  • 2 Software and its engineering → Software verification
  • 1 Computing methodologies → Spatial and physical reasoning
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 4 stochastic scheduling
  • 3 online algorithm
  • 3 scheduling
  • 3 stochastic programming
  • 2 State Machine Replication
  • Show More...

  • Refine by Type
  • 56 document

  • Refine by Publication Year
  • 32 2005
  • 15 2013
  • 2 2011
  • 2 2019
  • 1 2016
  • Show More...

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