117,603 research outputs found
Irredundant tandem motifs
No full textEliminating the possible redundancy from a set of candidate motifs occurring in an input string is fundamental in many applications. The existing techniques proposed to extract irredundant motifs are not suitable when the motifs to search for are structured, i.e., they are made of two (or several) subwords that co-occur in a text string s of length n. The main effort of this work is studying and characterizing a compact class of tandem motifs, that is, pairs of substrings {m1, m2} occurring in tandem within a maximum distance of d symbols in s, where d is an integer constant given in input. To this aim, we first introduce the concept of maximality, related to four specific conditions that hold only for this class of motifs. Then, we eliminate the remaining redundancy by defining the notion of irredundancy for tandem motifs. We prove that the number of non-overlapping irredundant tandem motifs is O(d2n) which, considering d as a constant, leads to a linear number of tandems in the length of the input string. This is an order of magnitude less than previously developed compact indexes for tandem extraction. The notions and bounds provided for tandem motifs are generalized for the case r≥2, if r is the number of subwords composing the motifs. Finally, we also provide an algorithm to extract irredundant tandem motifs
QUALITA DELLA CARNE DI ROMBO (Psetta maxima) ALLEVATO IN AMBIENTE CONDIZIONATO
No full textLa presente ricerca ha indagato sulla composizione chimica della carne di rombi allevati in un centro sperimentale per l’acquacoltura (CRIAcq) e di rombi acquistati presso la GDO provenienti da allevamenti esteri (Spagna). Il confronto ha interessato tre popolazioni di rombo chiodato, due (pop. A e B) allevate fino al raggiungimento della taglia commerciale nel sistema “a ricircolo” o “a ricircuitazione” del CRIAcq e una (pop. C) costituita da 20 soggetti acquistati dalla GDO. La determinazione delle frazioni analitiche e stata effettuata secondo le metodiche AOAC (1970). La significatività dei confronti tra le medie stimate è stata valutata con il “t” di Student. Le due popolazioni si sono adattate egregiamente al circuito chiuso evidenziando ottimi indici di accrescimento. Il peso medio dei rombi al momento delle analisi è risultato: 831,99 g per la popolazione A, 925,49 g per la B e 775,85 per la C. La composizione chimica percentuale delle popolazioni A e B è risultata significativamente diversa per il contenuto in sostanza secca e per il valore energetico, maggiore nella seconda. I rombi provenienti dalla GDO mediamente sono risultati avere, per 100 grammi di sostanza secca, un più elevato contenuto in lipidi (P<0,01) eun minor contenuto in ceneri (P<0,01) nei confronti di quelli allevati nel sistema a ricircolo
Characterization and Extraction of Irredundant Tandem Motifs
No full textWe address the problem of extracting pairs of subwords (m1,m2) from a text string s of length n, such that, given also an integer constant d in input, m1 and m2 occur in tandem within a maximum distance of d symbols in s.
The main effort of this work is to eliminate the possible redundancy from the candidate set of the so found tandem motifs. To this aim, we first introduce the concept of maximality, characterized by four specific conditions, that we show to be not deducible by the corresponding notion of maximality already defined for “simple” (i.e., non tandem) motifs. Then, we further eliminate the remaining redundancy by defining the concept of irredundancy for tandem motifs.
We prove that the number of non-overlapping irredundant tandems is O(d^2 n) which, considering d as a constant, leads to a linear number of tandems in the length of the input string. This is an order of magnitude less than previously developed compact indexes for tandem extraction. As a further contribution we show an algorithm to extract this compact irredundant index
Motif Patterns in 2D
No full textMotif patterns consisting of sequences of intermixed solid and don't-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms
Flexible Pattern Discovery with (Extended) Disjunctive Logic Programming
No full textThe post-genomic era showed up a wide range of new challenging issues for the areas of knowledge discovery and intelligent information management. Among them, the discovery of complex pattern repetitions in string databases plays an important role, specifically in those contexts where even what are to be considered the interesting pattern classes is unknown. This paper provides a contribution in this precise setting, proposing a novel approach, based on disjunctive logic programming extended with several advanced features, for discovering interesting pattern classes from a given data se
Entropic Profiles, Maximal Motifs and the Discovery of Significant Repetitions in Genomic Sequences
No full textThe degree of predictability of a sequence can be measured by its entropy and it is closely related to its repetitiveness and compressibility. Entropic profiles are useful tools to study the under- and over-representation of subsequences, providing also information about the scale of each conserved DNA region. On the other hand, compact classes of repetitive motifs, such as maximal motifs, have been proved to be useful for the identification of significant repetitions and for the compression of biological sequences. In this paper we show that there is a relationship between entropic profiles and maximal motifs, and in particular we prove that the former are a subset of the latter. As a further contribution we propose a novel linear time linear space algorithm to compute the function Entropic Profile introduced by Vinga and Almeida in [18], and we present some preliminary results on real data, showing the speed up of our approach with respect to other existing technique
FEDRO: a software tool for the automatic discovery of candidate ORFs in plants with c →u RNA editing
No full textBACKGROUND: RNA editing is an important mechanism for gene expression in plants organelles. It alters the direct transfer of genetic information from DNA to proteins, due to the introduction of differences between RNAs and the corresponding coding DNA sequences. Software tools successful for the search of genes in other organisms not always are able to correctly perform this task in plants organellar genomes. Moreover, the available software tools predicting RNA editing events utilise algorithms that do not account for events which may generate a novel start codon. RESULTS: We present Fedro, a Java software tool implementing a novel strategy to generate candidate Open Reading Frames (ORFs) resulting from Cytidine to Uridine (c→u) editing substitutions which occur in the mitochondrial genome (mtDNA) of a given input plant. The goal is to predict putative proteins of plants mitochondria that have not been yet annotated. In order to validate the generated ORFs, a screening is performed by checking for sequence similarity or presence in active transcripts of the same or similar organisms. We illustrate the functionalities of our framework on a model organism. CONCLUSIONS: The proposed tool may be used also on other organisms and genomes. Fedro is publicly available at http://math.unipa.it/rombo/FEDRO
A technique to search functional similarities in PPI networks
No full textWe describe a method to search for similarities across protein-protein interaction networks of different organisms. The technique core consists in computing a maximum weight matching of bipartite graphs resulting from comparing the neighbourhoods of proteins belonging to different networks. Both quantitative and reliability information are exploited. We tested the method on the networks of S. cerevisiae, D. melanogaster and C. elegans. The experiments showed that the technique is able to detect functional orthologs when the sole sequence similarity does not prove itself sufficient. They also demonstrated the capability of our approach in discovering common biological processes involving uncharacterised proteins
- …
