- Michael Elberfeld, Andreas Jakoby, Till Tantau:
Logspace Versions of the Theorems of Bodlaender and Courcelle.
In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), S. 143-152.
IEEE Computer Society,
2010.
Website anzeigen | Zusammenfassung anzeigen
Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for
every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.
- Michael Elberfeld, Till Tantau:
Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Band 6129 von Lecture Notes in Computer Science, S. 177-189.
Springer,
2010.
Website anzeigen | Zusammenfassung anzeigen
Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. In their CPM 2009 paper, Fellows et al. studied an extension of this approach that incorporates prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. While this approach may help to increase the accuracy of haplotyping methods, it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the present paper we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption.
- Maciej Liskiewicz, Johannes Textor:
Negative Selection Algorithms Without Generating Detectors.
In Proceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO'10), S. 1047-1054.
ACM,
2010.
PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
Negative selection algorithms are immune-inspired classifiers
that are trained on negative examples only. Classification
is performed by generating detectors that match none
of the negative examples, and these detectors are then
matched against the elements to be classified. This can be
a performance bottleneck: A large number of detectors may be required
for acceptable sensitivity, or finding detectors that match none of
the negative examples may be difficult.
In this paper, we show how negative selection can be implemented
without generating detectors explicitly, which for many detector
types leads to polynomial time algorithms whereas the common approach to
sample detectors randomly takes exponential time in the
worst case.
In particular, we show that negative selection on strings with
generating all detectors can be efficiently
simulated without detectors if, and only if, an associated
decision problem can be answered efficiently, regardless
the detector type. We also show how to efficiently
simulate the more general case in which only a limited
number of detectors is generated. For many detector types,
this non-exhaustive negative selection is more meaningful
but it can be computationally more difficult, which we illustrate
using Boolean monomials.
