Using sequence compression to speedup probabilistic profile matching

MOTIVATION

Matching a biological sequence against a probabilistic pattern (or profile) is a common task in computational biology. A probabilistic profile, represented as a scoring matrix, is more suitable than a deterministic pattern to retain the peculiarities of a given segment of a family of biological sequences. Brute-force algorithms take O(NP) to match a sequence of N characters against a profile of length P << N.

RESULTS

In this work, we exploit string compression techniques to speedup brute-force profile matching. We present two algorithms, based on run-length and LZ78 encodings, that reduce computational complexity by the compression factor of the encoding.

A Study on the Influence of Speed on Road Roughness Sensing: The SmartRoadSense Case

SmartRoadSense is a crowdsensing project aimed at monitoring the conditions of the road surface. Using the sensors of a smartphone, SmartRoadSense monitors the vertical accelerations inside a vehicle traveling the road and extracts a roughness index conveying information about the road conditions. The roughness index and the smartphone GPS data are periodically sent to a central server where they are processed, associated with the specific road, and aggregated with data measured by other smartphones. This paper studies how the smartphone vertical accelerations and the roughness index are related to the vehicle speed. It is shown that the dependence can be locally approximated with a gamma (power) law. Extensive experimental results using data extracted from SmartRoadSense database confirm the gamma law relationship between the roughness index and the vehicle speed. The gamma law is then used for improving the SmartRoadSense data aggregation accounting for the effect of vehicle speed.

Exploring Artificial Neural Networks Efficiency in Tiny Wearable Devices for Human Activity Recognition

The increasing diffusion of tiny wearable devices and, at the same time, the advent of machine learning techniques that can perform sophisticated inference, represent a valuable opportunity for the development of pervasive computing applications. Moreover, pushing inference on edge devices can in principle improve application responsiveness, reduce energy consumption and mitigate privacy and security issues. However, devices with small size and low-power consumption and factor form, like those dedicated to wearable platforms, pose strict computational, memory, and energy requirements which result in challenging issues to be addressed by designers. The main purpose of this study is to empirically explore this trade-off through the characterization of memory usage, energy consumption, and execution time needed by different types of neural networks (namely multilayer and convolutional neural networks) trained for human activity recognition on board of a typical low-power wearable device.Through extensive experimental results, obtained on a public human activity recognition dataset, we derive Pareto curves that demonstrate the possibility of achieving a 4× reduction in memory usage and a 36× reduction in energy consumption, at fixed accuracy levels, for a multilayer Perceptron network with respect to more sophisticated convolution network models.

A lossy compression technique enabling duplication-aware sequence alignment

In spite of the recognized importance of tandem duplications in genome evolution, commonly adopted sequence comparison algorithms do not take into account complex mutation events involving more than one residue at the time, since they are not compliant with the underlying assumption of statistical independence of adjacent residues. As a consequence, the presence of tandem repeats in sequences under comparison may impair the biological significance of the resulting alignment. Although solutions have been proposed, repeat-aware sequence alignment is still considered to be an open problem and new efficient and effective methods have been advocated. The present paper describes an alternative lossy compression scheme for genomic sequences which iteratively collapses repeats of increasing length. The resulting approximate representations do not contain tandem duplications, while retaining enough information for making their comparison even more significant than the edit distance between the original sequences. This allows us to exploit traditional alignment algorithms directly on the compressed sequences. Results confirm the validity of the proposed approach for the problem of duplication-aware sequence alignment.

Improved biological network reconstruction using graph Laplacian regularization

Biological networks reconstruction is a crucial step towards the functional characterization and elucidation of living cells. Computational methods for inferring the structure of these networks are of paramount importance since they provide valuable information regarding organization and behavior of the cell at a system level and also enable careful design of wet-lab experiments. Despite many recent advances, according to the scientific literature, there is room for improvements from both the efficiency and the accuracy point of view in link prediction algorithms. In this article, we propose a new method for the inference of biological networks that makes use of a notion of similarity between graph vertices within the framework of graph regularization for ranking the links to be predicted. The proposed approach results in more accurate classification rates in a wide range of experiments, while the computational complexity is reduced by two orders of magnitude with respect to many current state-of-the-art algorithms.

A monte carlo method for assessing the quality of duplication-aware alignment algorithms

The increasing availability of high throughput sequencing technologies poses several challenges concerning the analysis of genomic data. Within this context, duplication-aware sequence alignment taking into account complex mutation events is regarded as an important problem, particularly in light of recent evolutionary bioinformatics researches that highlighted the role of tandem duplications as one of the most important mutation events. Traditional sequence comparison algorithms do not take into account these events, resulting in poor alignments in terms of biological significance, mainly because of their assumption of statistical independence among contiguous residues. Several duplication-aware algorithms have been proposed in the last years which differ either for the type of duplications they consider or for the methods adopted to identify and compare them. However, there is no solution which clearly outperforms the others and no methods exist for assessing the reliability of the resulting alignments. This paper proposes a Monte Carlo method for assessing the quality of duplication-aware alignment algorithms and for driving the choice of the most appropriate alignment technique to be used in a specific context.

The applicability and usefulness of the proposed approach are demonstrated on a case study, namely, the comparison of alignments based on edit distance with or without repeat masking.

Nrf2-Mediated Pathway Activated by Prunus spinosa L. (Rosaceae) Fruit Extract: Bioinformatics Analyses and Experimental Validation

In our previous studies, Prunus spinosa fruit (PSF) ethanol extract was showed to exert antioxidant, antimicrobial, anti-inflammatory and wound healing activities. In the present study, an integrated bioinformatics analysis combined with experimental validation was carried out to investigate the biological mechanism(s) that are responsible for the reported PSF beneficial effects as an antioxidant during a pro-inflammatory TLR4 insult. Bioinformatics analysis using miRNet 2.0 was carried out to address which biological process(es) the extract could be involved in. In addition, Chemprop was employed to identify the key targets of nuclear receptor (NR) signaling and stress response (SR) pathways potentially modulated. The miRNet analysis suggested that the PSF extract mostly activates the biological process of cellular senescence. The Chemprop analysis predicted three possible targets for nine phytochemicals found in the extract: (i) ARE signaling, (ii) mitochondrial membrane potential (MMP) and (iii) p53 SR pathways. The PSF extract antioxidant effect was also experimentally validated in vitro using the human monocyte U937 cell line. Our findings showed that Nrf2 is modulated by the extract with a consequent reduction of the oxidative stress level. This was confirmed by a strong decrease in the amount of reactive oxygen species (ROS) observed in the PSF-treated cells subjected to lipopolysaccharide (LPS) (6 h treatment, 1 µg/mL). No visible effects were observed on p53 and MMP modulation.

Evaluation of a sampling approach for computationally efficient uncertainty quantification in regression learning models

The capability of effectively quantifying the uncertainty associated to a given prediction is an important task in many applications that range from drug design to autonomous driving, providing valuable information to many downstream decision-making processes. The increasing capacity of novel machine learning models, and the growing amount of data on which these systems are trained poses however significant issues to be addressed. Recent research advocated the need for evaluating learning systems not only according to traditional accuracy metrics but also according to the computational complexity required to design them, toward a perspective of sustainability and inclusivity. In this work, we present an empirical investigation aimed at assessing the impact of uniform sampling on the reduction in computational requirements, the quality of regression, and on its uncertainty quantification. We performed several experiments with recent state-of-the-art methods characterized by statistical guarantees whose performances have been measured according to different metrics for evaluating uncertainty quantification (i.e., coverage and length of prediction intervals) and regression (i.e., errors measures and correlation). Experimental results highlight possible interesting trade-offs between computation time, regression and uncertainty evaluation quality, thus confirming the viability of sampling-based approaches to overcome computational bottlenecks without significantly affecting the quality of predictions.

Genome-wide computational approach for the prediction of duplications generating protein localization signals

Investigating the possible generation of motifs accountable for aberrant protein dislocation subsequent to the rise of short tandem duplications is interesting, given the pathogenic potential of this mechanism, as demonstrated in diseases such adult myeloid leukemia (AML). In this paper we introduce a new computational method for predicting genomic points which, after hypothetical mutation events such as micro-duplications, might encode molecular patterns such as localization or export signals. The proposed framework allows to study motifs of unconstrained length defined as regular expressions at a genome-wide level, providing an in silico platform capable of analyzing the potential effect of duplications on abnormal cellular localization.