- Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-private Environments.
Theory of Computing Systems, 48(1):211-245, 2011.
Go to website - Michael Elberfeld, Johannes Textor:
Negative Selection Algorithms on Strings with Efficient Training and Linear-Time Classification.
Theoretical Computer Science, 412(6):534-542, 2011.
Show PDF | Go to website | Show abstract
A string-based negative selection algorithm is an immune-inspired
classifier that infers a partitioning of a string space $\Sigma^\ell$
into ``normal'' and ``anomalous'' partitions from a training set $S$
containing only samples from the ``normal'' partition.
The algorithm generates a set of patterns, called ``detectors'', to cover
regions of the string space containing none of the training samples.
Strings that match at least one of these detectors are then
classified as ``anomalous''. A major problem with existing
implementations of this approach is that the detector generation step suffers
from exponential worst-case time complexity.
Hence, researchers have found negative selection to be of
limited use for real-world problems such as network intrusion detection.
Here we show that for the two most widely used kinds of detectors, the
$r$-chunk and $r$-contiguous detectors based on partial matching
to substrings of length $r$, negative selection can be
implemented efficiently by avoiding generating detectors
altogether: For each detector type, training set
$S\subseteq\Sigma^\ell$ and parameter $r \leq \ell$ one can construct an
automaton whose acceptance behaviour is
equivalent to the algorithm's
classification outcome. The resulting runtime
is $O(|S|\ell r|\Sigma|)$ for constructing the automaton in
the training phase and $O(\ell)$ for classifying a string.
- Michael Elberfeld, Vineet Bafna, Iftah Gamzu, Alexander Medvedovsky, Danny Segev, Dana Silverbush, Uri Zwick, Roded Sharan:
On the Approximability of Reachability-Preserving Network Orientations.
Internet Mathematics, 4(7):209-232, 2011.
Show PDF | Go to website | Show abstract
We introduce a graph orientation problem arising in the study of
biological networks. Given an undirected graph and a list of ordered
source-target vertex pairs, the goal is to orient the graph such that
a maximum number of pairs admit a directed source-to-target path. We
study the complexity and approximability of this problem. We show that
the problem is NP-hard even on star graphs and hard to
approximate to within some constant factor. On the positive side, we
provide an $\Omega(\log\log n / \log n)$-factor approximation
algorithm for the problem on n-vertex graphs. We further show that
for any instance of the problem there exists an orientation of the
input graph that satisfies a logarithmic fraction of all pairs and
that this bound is tight up to a constant factor. Our techniques also
lead to constant factor approximation algorithms for some restricted
variants of the problem.
- Markus Hinkelmann, Andreas Jakoby, Nina Moebius, Tiark Rompf, Peer Stechert:
A cryptographically t-private auction system.
Concurrency and Computation: Practice and Experience, 12(23):1399–1413, 2011.
- Christian Hundt, Maciej Liskiewicz:
New complexity bounds for image matching under rotation and scaling.
Journal of Discrete Algorithms, 9:122–136, 2011.
Go to website - Dana Silverbush, Michael Elberfeld, Roded Sharan:
Optimally Orienting Physical Networks.
Journal of Computational Biology, 18(11):1437-1448, 2011.
Go to website | Show abstract
In a network orientation problem one is given a mixed graph,
consisting of directed and undirected edges, and a set
of source-target vertex pairs. The goal is to orient the undirected edges
so that a maximum number of pairs admit a directed path from the source to the
target. This NP-complete problem arises in the context of
analyzing physical networks of protein-protein and protein-DNA
interactions. While the latter are
naturally directed from a transcription factor to a gene, the
direction of signal flow
in protein-protein interactions is often unknown or cannot
be measured en masse. One then tries to infer
this information by using causality data on pairs of genes such that the
perturbation of one gene changes the expression level of the other gene.
Here we provide a first polynomial-size ILP formulation
for this problem, which can be efficiently solved on current networks.
We apply our
algorithm to orient protein-protein interactions in yeast and measure our
performance using edges with known orientations. We find that our algorithm
achieves high accuracy and coverage in the orientation,
outperforming simplified algorithmic variants that do not use
information on edge directions. The obtained orientations can lead to
a better understanding of the structure and function of the network.
- Johannes Textor, Juliane Hardt, Sven Knüppel:
DAGitty: A Graphical Tool for Analyzing Causal Diagrams.
Epidemiology, 5(22):745, 2011.
Go to website - Johannes Textor, Antonio Peixoto, Sarah E. Henrickson, Mathieu Sinn, Ulrich H. von Andrian, Jürgen Westermann:
Defining the Quantitative Limits of Intravital Two-Photon Lymphocyte Tracking.
Proceedings of the National Academy of Sciences of the United States of America, 108(30):12401-12406, 2011.
Go to website | Show abstract
Two-photon microscopy has substantially advanced our understanding of cellular dynamics in the immune system. Cell migration can now be imaged in real time in the living animal. Strikingly, the migration of naive lymphocytes in secondary lymphoid tissue appears predominantly random. It is unclear, however, whether directed migration may escape detection in this random background. Using a combination of mathematical modeling and experimental data, we investigate the extent to which modern two-photon imaging can rule out biologically relevant directed migration. For naive T cells migrating in uninfected lymph nodes (LNs) at average 3D speeds of around 18 ?m/min, we rule out uniform directed migration of more than 1.7 ?m/min at the 95% confidence level, confirming that T cell migration is indeed mostly random on a timescale of minutes. To investigate whether this finding still holds for longer timescales, we use a 3D simulation of the naive T cell LN transit. A pure random walk predicts a transit time of around 16 h, which is in good agreement with experimental results. A directional bias of only 0.5 ?m/min—less than 3% of the cell speed—would already accelerate the transit twofold. These results jointly strengthen the random walk analogy for naive T cell migration in LNs, but they also emphasize that very small deviations from random migration can still be important. Our methods are applicable to cells of any type and can be used to reanalyze existing datasets.
