An algebraic language for RNA pseudoknots comparison
Abstract 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 wo...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2019-04-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12859-019-2689-5 |
| _version_ | 1811224467306708992 |
|---|---|
| author | Michela Quadrini Luca Tesei Emanuela Merelli |
| author_facet | Michela Quadrini Luca Tesei Emanuela Merelli |
| author_sort | Michela Quadrini |
| collection | DOAJ |
| description | Abstract 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. |
| first_indexed | 2024-04-12T08:49:54Z |
| format | Article |
| id | doaj.art-dcb808a05d114dc18a3b0f5782b6747d |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-04-12T08:49:54Z |
| publishDate | 2019-04-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-dcb808a05d114dc18a3b0f5782b6747d2022-12-22T03:39:37ZengBMCBMC Bioinformatics1471-21052019-04-0120S411810.1186/s12859-019-2689-5An algebraic language for RNA pseudoknots comparisonMichela Quadrini0Luca Tesei1Emanuela Merelli2School of Science and Technology, University of CamerinoSchool of Science and Technology, University of CamerinoSchool of Science and Technology, University of CamerinoAbstract 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.http://link.springer.com/article/10.1186/s12859-019-2689-5Tree grammarTree alignmentAlgebraic RNA treeStructural RNA treeASPRA distance |
| spellingShingle | Michela Quadrini Luca Tesei Emanuela Merelli An algebraic language for RNA pseudoknots comparison BMC Bioinformatics Tree grammar Tree alignment Algebraic RNA tree Structural RNA tree ASPRA distance |
| title | An algebraic language for RNA pseudoknots comparison |
| title_full | An algebraic language for RNA pseudoknots comparison |
| title_fullStr | An algebraic language for RNA pseudoknots comparison |
| title_full_unstemmed | An algebraic language for RNA pseudoknots comparison |
| title_short | An algebraic language for RNA pseudoknots comparison |
| title_sort | algebraic language for rna pseudoknots comparison |
| topic | Tree grammar Tree alignment Algebraic RNA tree Structural RNA tree ASPRA distance |
| url | http://link.springer.com/article/10.1186/s12859-019-2689-5 |
| work_keys_str_mv | AT michelaquadrini analgebraiclanguageforrnapseudoknotscomparison AT lucatesei analgebraiclanguageforrnapseudoknotscomparison AT emanuelamerelli analgebraiclanguageforrnapseudoknotscomparison AT michelaquadrini algebraiclanguageforrnapseudoknotscomparison AT lucatesei algebraiclanguageforrnapseudoknotscomparison AT emanuelamerelli algebraiclanguageforrnapseudoknotscomparison |