| CARVIEW |
GenussFold: MCFGs for Genus-1 RNA Pseudoknots
generalized Algebraic Dynamic Programming
Genus-1 RNA pseudoknot grammars implemented with a multiple context-free language. Compared to the usual implementations that are based on explicit recursions, an implementation based on a formal grammar is much more pleasing to write.
Consult the README for details.
BioInf.GenussFold.PKN: Recursive pseudoknots with a simple basepair maximization scoring scheme.
[Skip to Readme]
Flags
Manual Flags
| Name | Description | Default |
|---|---|---|
| debug | dump intermediate Core files | Disabled |
Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info
Downloads
- GenussFold-0.0.0.2.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
| Versions [RSS] | 0.0.0.1, 0.0.0.2 |
|---|---|
| Change log | changelog.md |
| Dependencies | ADPfusion (>=0.4.1.1 && <0.4.2), ansi-wl-pprint (>=0.6.7 && <0.6.8), base (>=4.7 && <4.9), bytestring (>=0.10 && <0.11), cmdargs (>=0.10 && <0.11), containers, data-default (>=0.5 && <0.6), FormalGrammars (>=0.2.1 && <0.2.2), GenussFold, lens (>=4.0 && <5.0), mtl (>=2.0 && <3.0), PrimitiveArray (>=0.6.0 && <0.6.2), semigroups (>=0.16 && <0.17), template-haskell, text (>=1.0 && <1.3), transformers (>=0.3 && <0.5), unordered-containers (>=0.2 && <0.3), vector (>=0.10 && <0.11) [details] |
| Tested with | ghc ==7.8.4, ghc ==7.10.1 |
| License | GPL-3.0-only |
| Copyright | Christian Hoener zu Siederdissen, 2015 |
| Author | Christian Hoener zu Siederdissen, 2015 |
| Maintainer | choener@bioinf.uni-leipzig.de |
| Uploaded | by ChristianHoener at 2015-07-16T17:51:09Z |
| Category | Formal Languages, Bioinformatics |
| Home page | https://github.com/choener/GenussFold |
| Bug tracker | https://github.com/choener/GenussFold/issues |
| Source repo | head: git clone git://github.com/choener/GenussFold |
| Distributions | |
| Executables | GenussFold |
| Downloads | 1842 total (6 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating |
|
| Status | Docs available [build log] Last success reported on 2015-07-16 [all 1 reports] |
Readme for GenussFold-0.0.0.2
[back to package description]
GenussFold: RNA Pseudoknot Folding
generalized Algebraic Dynamic Programming Homepage
The implementation makes use of the gADP technique and provides a larger example on how to implement algorithms that require interleaved, split syntactic variables.
Formal background can be found in this paper:
Maik Riechert, Christian Höner zu Siederdissen, and Peter F. Stadler
Algebraic dynamic programming for multiple context-free languages
2015, submitted
preprint
As an example, consider palindromic brackets ((())). Given two types of
brackets, these can be interleaved: ((( [[[ ))) ]]]. Such interleaved,
long-range dependencies have been observed in human languages and, in
particular, in RNA bioinformatics.
RNA structures may form so-called pseudoknots, where the RNA structure does not
yield a planar structure (the canonical secondary structure) anymore, but
rather forms graphs with crossing edges. Using the idea of interleaved brackets
and given an input sequence AAA CCC UUU GGG (with artificial white space to
make this more clear), a pseudoknotted structure may be formed:
AAA CCC UUU GGG
[[[ ((( ]]] )))
A formal grammar that parses such a structure requires the ability to denote that a sub-structure has a "hole". We can write such a grammar as follows:
S -> U V U V
<U,U> -> [ε,ε]
<U,U> -> [S,-] [a,-] <U,U> [-,S] [-,u]
<V,V> -> [ε,ε]
<V,V> -> [S,-] [c,-] <V,V> [-,S] [-,g]
The PKN grammar in GenussFold (for genus-1 structures, but much more
pleasurable to write) offers the required features:
- state that a syntactic variable is split between two regions
<U,U> - state that this split system is linearized and different symbols can be
interleaved:
U V U V - in addition, we allow syntactic variables of lower dimension (like
S) to be used in dimensional stacks of symbols ([S,-]).
This system allows writing monotone multiple context-free grammars with good performance -- we are reasonably close to C in running time performance. Reasonable means around a factor of 2 slower.
Performance comparison
C-code for running time performance comparison is available in the GenussFold github repository. The direct URL is: https://github.com/choener/GenussFold/blob/master/C/genussfold.c
Contact
Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
choener@bioinf.uni-leipzig.de
https://www.bioinf.uni-leipzig.de/~choener/