Detecting local common sequence-structure regions of RNAs is a biologically important problem. Detecting such regions allows biologists to identify functionally relevant similarities between the inspected molecules. We developed dynamic programming algorithms for finding common structure-sequence patterns between two RNAs. The RNAs are given by their sequence and a set of potential base pairs with associated probabilities. In contrast to prior work on local pattern matching of RNAs, we support the breaking of arcs. This allows us to add flexibility over matching only fixed structures; potentially matching only a similar subset of specified base pairs. We present an O(n(3)) algorithm for local exact pattern matching between two nested RNAs, and an O(n(3) log n) algorithm for one nested RNA and one bounded-unlimited RNA. In addition, an algorithm for approximate pattern matching is introduced that for two given nested RNAs and a number k, finds the maximal local pattern matching score between the two RNAs with at most k mismatches in O(n(3)k(2)) time. Finally, we present an O(n(3)) algorithm for finding the most similar subforest between two nested RNAs.

Download full-text PDF

Source
http://dx.doi.org/10.1109/TCBB.2013.2297113DOI Listing

Publication Analysis

Top Keywords

pattern matching
20
nested rnas
12
local exact
8
exact pattern
8
rnas
8
base pairs
8
local pattern
8
on3 algorithm
8
matching
7
local
5

Similar Publications

Powder X-ray diffraction (PXRD) is a prevalent technique in materials characterization. While the analysis of PXRD often requires extensive human manual intervention, and most automated method only achieved at coarse-grained level. The more difficult and important task of fine-grained crystal structure prediction from PXRD remains unaddressed.

View Article and Find Full Text PDF

Background: Contemporary guidelines advocate for initial debridement and single-stage definitive fixation with immediate soft tissue reconstruction for open fractures. This study aims to evaluate the effectiveness of single-stage stabilization and immediate definitive soft tissue coverage in open ankle fractures compared to closed fractures.

Methods: We compared all isolated open ankle fractures (OF) treated between January 2017 and June 2019 to a control group of operatively managed closed ankle fractures (CF).

View Article and Find Full Text PDF

Background: Modern dietary trends have led to an increase in foods that are relatively high in n-6 polyunsaturated fatty acids (PUFAs) and low in n-3 PUFAs. We previously reported that the offspring of mother mice that consumed a diet high in n-6 linoleic acid (LA) and low in n-3 α-linolenic acid (ALA), hereinafter called the LA/ALA diet, exhibit behavioral abnormalities related to anxiety and feeding.

Objective: We currently lack a comprehensive overview of the behavioral abnormalities in these offspring, which was investigated in this study.

View Article and Find Full Text PDF

Face pareidolia minimally engages macaque face selective neurons.

Prog Neurobiol

January 2025

Section on Cognitive Neurophysiology and Imaging, National Institute of Mental Health; Bethesda, MD, USA; Neurophysiology Imaging Facility, National Institute of Mental Health, National Institute of Neurological Disorders and Stroke, National Eye Institute; Bethesda, MD, USA. Electronic address:

The macaque cerebral cortex contains concentrations of neurons that prefer faces over inanimate objects. Although these so-called face patches are thought to be specialized for the analysis of facial signals, their exact tuning properties remain unclear. For example, what happens when an object by chance resembles a face? Everyday objects can sometimes, through the accidental positioning of their internal components, appear as faces.

View Article and Find Full Text PDF

Theory of morphodynamic information processing: Linking sensing to behaviour.

Vision Res

January 2025

Centre for Brain and Behaviour, School of Biological and Behavioural Sciences, Queen Mary University of London, London E1 4NS, UK.

The traditional understanding of brain function has predominantly focused on chemical and electrical processes. However, new research in fruit fly (Drosophila) binocular vision reveals ultrafast photomechanical photoreceptor movements significantly enhance information processing, thereby impacting a fly's perception of its environment and behaviour. The coding advantages resulting from these mechanical processes suggest that similar physical motion-based coding strategies may affect neural communication ubiquitously.

View Article and Find Full Text PDF

Want AI Summaries of new PubMed Abstracts delivered to your In-box?

Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!