@article{CaselDreierFernauetal.2020, author = {Casel, Katrin and Dreier, Jan and Fernau, Henning and Gobbert, Moritz and Kuinke, Philipp and Villaamil, Fernando S{\´a}nchez and Schmid, Markus L. and van Leeuwen, Erik Jan}, title = {Complexity of independency and cliquy trees}, series = {Discrete applied mathematics}, volume = {272}, journal = {Discrete applied mathematics}, publisher = {Elsevier}, address = {Amsterdam [u.a.]}, issn = {0166-218X}, doi = {10.1016/j.dam.2018.08.011}, pages = {2 -- 15}, year = {2020}, abstract = {An independency (cliquy) tree of an n-vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4(k))-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18(k))-time algorithm and an O(k 2(k)) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3(n) . f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size.}, language = {en} } @article{ZaliOhrnbergerScherbaumetal.2021, author = {Zali, Zahra and Ohrnberger, Matthias and Scherbaum, Frank and Cotton, Fabrice and Eibl, Eva P. S.}, title = {Volcanic tremor extraction and earthquake detection using music information retrieval algorithms}, series = {Seismological research letters}, volume = {92}, journal = {Seismological research letters}, number = {6}, publisher = {Seismological Society of America}, address = {Boulder, Colo.}, issn = {0895-0695}, doi = {10.1785/0220210016}, pages = {3668 -- 3681}, year = {2021}, abstract = {Volcanic tremor signals are usually observed before or during volcanic eruptions and must be monitored to evaluate the volcanic activity. A challenge in studying seismic signals of volcanic origin is the coexistence of transient signal swarms and long-lasting volcanic tremor signals. Separating transient events from volcanic tremors can, therefore, contrib-ute to improving upon our understanding of the underlying physical processes. Exploiting the idea of harmonic-percussive separation in musical signal processing, we develop a method to extract the harmonic volcanic tremor signals and to detect tran-sient events from seismic recordings. Based on the similarity properties of spectrogram frames in the time-frequency domain, we decompose the signal into two separate spec-trograms representing repeating (harmonic) and nonrepeating (transient) patterns, which correspond to volcanic tremor signals and earthquake signals, respectively. We reconstruct the harmonic tremor signal in the time domain from the complex spectrogram of the repeating pattern by only considering the phase components for the frequency range in which the tremor amplitude spectrum is significantly contribut-ing to the energy of the signal. The reconstructed signal is, therefore, clean tremor signal without transient events. Furthermore, we derive a characteristic function suitable for the detection of tran-sient events (e.g., earthquakes) by integrating amplitudes of the nonrepeating spectro-gram over frequency at each time frame. Considering transient events like earthquakes, 78\% of the events are detected for signal-to-noise ratio = 0.1 in our semisynthetic tests. In addition, we compared the number of detected earthquakes using our method for one month of continuous data recorded during the Holuhraun 2014-2015 eruption in Iceland with the bulletin presented in Agustsdottir et al. (2019). Our single station event detection algorithm identified 84\% of the bulletin events. Moreover, we detected a total of 12,619 events, which is more than twice the number of the bulletin events.}, language = {en} } @article{KreowskyStabernack2021, author = {Kreowsky, Philipp and Stabernack, Christian Benno}, title = {A full-featured FPGA-based pipelined architecture for SIFT extraction}, series = {IEEE access : practical research, open solutions / Institute of Electrical and Electronics Engineers}, volume = {9}, journal = {IEEE access : practical research, open solutions / Institute of Electrical and Electronics Engineers}, publisher = {Inst. of Electr. and Electronics Engineers}, address = {New York, NY}, issn = {2169-3536}, doi = {10.1109/ACCESS.2021.3104387}, pages = {128564 -- 128573}, year = {2021}, abstract = {Image feature detection is a key task in computer vision. Scale Invariant Feature Transform (SIFT) is a prevalent and well known algorithm for robust feature detection. However, it is computationally demanding and software implementations are not applicable for real-time performance. In this paper, a versatile and pipelined hardware implementation is proposed, that is capable of computing keypoints and rotation invariant descriptors on-chip. All computations are performed in single precision floating-point format which makes it possible to implement the original algorithm with little alteration. Various rotation resolutions and filter kernel sizes are supported for images of any resolution up to ultra-high definition. For full high definition images, 84 fps can be processed. Ultra high definition images can be processed at 21 fps.}, language = {en} } @article{Mischke2021, author = {Mischke, Dennis}, title = {Deleuze and the digital}, series = {Deleuze and Guattari studies}, volume = {15}, journal = {Deleuze and Guattari studies}, number = {4}, publisher = {Edinburgh University Press}, address = {Edinburgh}, issn = {2398-9777}, doi = {10.3366/dlgs.2021.0459}, pages = {593 -- 609}, year = {2021}, abstract = {In his short and often quoted essay 'Postscript on the Societies of Control', Gilles Deleuze famously describes the structures of power in the dawning twenty-first century as driven by 'machines of a third type, computers', as novel and predominantly digital infrastructures. In fact, from a Deleuzian perspective the entire ecosystem of the digital transformation can be described as a larger shift in modes of production and the political economy. This essay proposes to read this 'technological evolution' as the power of algorithms and their material substance - digital infrastructures that entail a different mode of interaction between humans and technology. In looking at these infrastructures from a materialist position, my essay reconceptualises the digital as the unfolding logic of assemblages that have been shaping a 'long now' of technological modernity. In bringing a Deleuzian reading of infrastructures to the study of technology and society, this essay seeks to shed a new light on the political function-and the increasing abstraction-of infrastructures in the realm of the digital.}, language = {en} } @misc{HempelKoseskaNikoloskietal.2017, author = {Hempel, Sabrina and Koseska, Aneta and Nikoloski, Zoran and Kurths, J{\"u}rgen}, title = {Unraveling gene regulatory networks from time-resolved gene expression data}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-400924}, pages = {26}, year = {2017}, abstract = {Background: Inferring regulatory interactions between genes from transcriptomics time-resolved data, yielding reverse engineered gene regulatory networks, is of paramount importance to systems biology and bioinformatics studies. Accurate methods to address this problem can ultimately provide a deeper insight into the complexity, behavior, and functions of the underlying biological systems. However, the large number of interacting genes coupled with short and often noisy time-resolved read-outs of the system renders the reverse engineering a challenging task. Therefore, the development and assessment of methods which are computationally efficient, robust against noise, applicable to short time series data, and preferably capable of reconstructing the directionality of the regulatory interactions remains a pressing research problem with valuable applications. Results: Here we perform the largest systematic analysis of a set of similarity measures and scoring schemes within the scope of the relevance network approach which are commonly used for gene regulatory network reconstruction from time series data. In addition, we define and analyze several novel measures and schemes which are particularly suitable for short transcriptomics time series. We also compare the considered 21 measures and 6 scoring schemes according to their ability to correctly reconstruct such networks from short time series data by calculating summary statistics based on the corresponding specificity and sensitivity. Our results demonstrate that rank and symbol based measures have the highest performance in inferring regulatory interactions. In addition, the proposed scoring scheme by asymmetric weighting has shown to be valuable in reducing the number of false positive interactions. On the other hand, Granger causality as well as information-theoretic measures, frequently used in inference of regulatory networks, show low performance on the short time series analyzed in this study. Conclusions: Our study is intended to serve as a guide for choosing a particular combination of similarity measures and scoring schemes suitable for reconstruction of gene regulatory networks from short time series data. We show that further improvement of algorithms for reverse engineering can be obtained if one considers measures that are rooted in the study of symbolic dynamics or ranks, in contrast to the application of common similarity measures which do not consider the temporal character of the employed data. Moreover, we establish that the asymmetric weighting scoring scheme together with symbol based measures (for low noise level) and rank based measures (for high noise level) are the most suitable choices.}, language = {en} } @article{KlieNikoloskiSelbig2014, author = {Klie, Sebastian and Nikoloski, Zoran and Selbig, Joachim}, title = {Biological cluster evaluation for gene function prediction}, series = {Journal of computational biology}, volume = {21}, journal = {Journal of computational biology}, number = {6}, publisher = {Liebert}, address = {New Rochelle}, issn = {1066-5277}, doi = {10.1089/cmb.2009.0129}, pages = {428 -- 445}, year = {2014}, abstract = {Recent advances in high-throughput omics techniques render it possible to decode the function of genes by using the "guilt-by-association" principle on biologically meaningful clusters of gene expression data. However, the existing frameworks for biological evaluation of gene clusters are hindered by two bottleneck issues: (1) the choice for the number of clusters, and (2) the external measures which do not take in consideration the structure of the analyzed data and the ontology of the existing biological knowledge. Here, we address the identified bottlenecks by developing a novel framework that allows not only for biological evaluation of gene expression clusters based on existing structured knowledge, but also for prediction of putative gene functions. The proposed framework facilitates propagation of statistical significance at each of the following steps: (1) estimating the number of clusters, (2) evaluating the clusters in terms of novel external structural measures, (3) selecting an optimal clustering algorithm, and (4) predicting gene functions. The framework also includes a method for evaluation of gene clusters based on the structure of the employed ontology. Moreover, our method for obtaining a probabilistic range for the number of clusters is demonstrated valid on synthetic data and available gene expression profiles from Saccharomyces cerevisiae. Finally, we propose a network-based approach for gene function prediction which relies on the clustering of optimal score and the employed ontology. Our approach effectively predicts gene function on the Saccharomyces cerevisiae data set and is also employed to obtain putative gene functions for an Arabidopsis thaliana data set.}, language = {en} }