ABSTRACT
BACKGROUND: The ability to compare RNA secondary structures is important in understanding their biological function and for grouping similar organisms into families by looking at evolutionarily conserved sequences such as 16S rRNA. Most comparison methods and benchmarks in the literature focus on pseudoknot-free structures due to the difficulty of mapping pseudoknots in classical tree representations. Some approaches exist that permit to cluster pseudoknotted RNAs but there is not a general framework for evaluating their performance. RESULTS: We introduce an evaluation framework based on a similarity/dissimilarity measure obtained by a comparison method and agglomerative clustering. Their combination automatically partition a set of molecules into groups. To illustrate the framework we define and make available a benchmark of pseudoknotted (16S and 23S) and pseudoknot-free (5S) rRNA secondary structures belonging to Archaea, Bacteria and Eukaryota. We also consider five different comparison methods from the literature that are able to manage pseudoknots. For each method we clusterize the molecules in the benchmark to obtain the taxa at the rank phylum according to the European Nucleotide Archive curated taxonomy. We compute appropriate metrics for each method and we compare their suitability to reconstruct the taxa.
Subject(s)
Algorithms , RNA , Humans , Nucleic Acid Conformation , RNA, Ribosomal, 16S/genetics , RNA/genetics , RNA, Ribosomal/genetics , Archaea/geneticsABSTRACT
SUMMARY: Current methods for comparing RNA secondary structures are based on tree representations and exploit edit distance or alignment algorithms. Most of them can only process structures without pseudoknots. To overcome this limitation, we introduce ASPRAlign, a Java tool that aligns particular algebraic tree representations of RNA. These trees neglect the primary sequence and can handle structures with arbitrary pseudoknots. A measure of comparison, called ASPRA distance, is computed with a worst-case time complexity of O(n2) where n is the number of nucleotides of the longer structure. AVAILABILITY AND IMPLEMENTATION: ASPRAlign is implemented in Java and source code is released under the GNU GPLv3 license. Code and documentation are freely available at https://github.com/bdslab/aspralign. CONTACT: luca.tesei@unicam.it. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.
Subject(s)
RNA , Software , Algorithms , Protein Structure, Secondary , Sequence Analysis, RNAABSTRACT
BACKGROUND: RNA secondary structure comparison is a fundamental task for several studies, among which are RNA structure prediction and evolution. The comparison can currently be done efficiently only for pseudoknot-free structures due to their inherent tree representation. RESULTS: In this work, we introduce an algebraic language to represent RNA secondary structures with arbitrary pseudoknots. Each structure is associated with a unique algebraic RNA tree that is derived from a tree grammar having concatenation, nesting and crossing as operators. From an algebraic RNA tree, an abstraction is defined in which the primary structure is neglected. The resulting structural RNA tree allows us to define a new measure of similarity calculated exploiting classical tree alignment. CONCLUSIONS: The tree grammar with its operators permit to uniquely represent any RNA secondary structure as a tree. Structural RNA trees allow us to perform comparison of RNA secondary structures with arbitrary pseudoknots without taking into account the primary structure.
Subject(s)
Algorithms , Nucleic Acid Conformation , RNA/chemistry , Base Sequence , Sequence AlignmentABSTRACT
OBJECTIVE: An innovative method based on topological data analysis is introduced for classifying EEG recordings of patients affected by epilepsy. We construct a topological space from a collection of EEGs signals using Persistent Homology; then, we analyse the space by Persistent entropy, a global topological feature, in order to classify healthy and epileptic signals. RESULTS: The performance of the resulting one-feature-based linear topological classifier is tested by analysing the Physionet dataset. The quality of classification is evaluated in terms of the Area Under Curve (AUC) of the receiver operating characteristic curve. It is shown that the linear topological classifier has an AUC equal to [Formula: see text] while the performance of a classifier based on Sample Entropy has an AUC equal to 62.0%.
Subject(s)
Electroencephalography/methods , Seizures/diagnosis , Signal Processing, Computer-Assisted , Algorithms , Child , Electroencephalography/classification , Entropy , Humans , Seizures/classification , Seizures/physiopathologyABSTRACT
Software agents are particularly suitable for engineering models and simulations of cellular systems. In a very natural and intuitive manner, individual software components are therein delegated to reproduce "in silico" the behavior of individual components of alive systems at a given level of resolution. Individuals' actions and interactions among individuals allow complex collective behavior to emerge. In this chapter we first introduce the readers to software agents and multi-agent systems, reviewing the evolution of agent-based modeling of biomolecular systems in the last decade. We then describe the main tools, platforms, and methodologies available for programming societies of agents, possibly profiting also of toolkits that do not require advanced programming skills.