dorsal/arxiv
View SchemaRNA secondary structure design
| Authors | Bernd Burghardt, Alexander K. Hartmann |
|---|---|
| Categories | |
| ArXiv ID | physics/0609135 |
| URL | https://arxiv.org/abs/physics/0609135 |
| DOI | 10.1103/PhysRevE.75.021920 |
Abstract
We consider the inverse-folding problem for RNA secondary structures: for a given (pseudo-knot-free) secondary structure find a sequence that has that structure as its ground state. If such a sequence exists, the structure is called designable. We implemented a branch-and-bound algorithm that is able to do an exhaustive search within the sequence space, i.e., gives an exact answer whether such a sequence exists. The bound required by the branch-and-bound algorithm are calculated by a dynamic programming algorithm. We consider different alphabet sizes and an ensemble of random structures, which we want to design. We find that for two letters almost none of these structures are designable. The designability improves for the three-letter case, but still a significant fraction of structures is undesignable. This changes when we look at the natural four-letter case with two pairs of complementary bases: undesignable structures are the exception, although they still exist. Finally, we also study the relation between designability and the algorithmic complexity of the branch-and-bound algorithm. Within the ensemble of structures, a high average degree of undesignability is correlated to a long time to prove that a given structure is (un-)designable. In the four-letter case, where the designability is high everywhere, the algorithmic complexity is highest in the region of naturally occurring RNA.
{
"annotation_id": "39e0543f-abf8-4f40-9adc-148be70c4574",
"date_created": "2026-03-02T18:01:10.857000Z",
"date_modified": "2026-03-02T18:01:10.857000Z",
"file_hash": "131d6530cf52463b96765e8ca75c9afbb0db1f40ff1aba82369fc326e1013035",
"private": false,
"record": {
"abstract": "We consider the inverse-folding problem for RNA secondary structures: for a\ngiven (pseudo-knot-free) secondary structure find a sequence that has that\nstructure as its ground state. If such a sequence exists, the structure is\ncalled designable. We implemented a branch-and-bound algorithm that is able to\ndo an exhaustive search within the sequence space, i.e., gives an exact answer\nwhether such a sequence exists. The bound required by the branch-and-bound\nalgorithm are calculated by a dynamic programming algorithm. We consider\ndifferent alphabet sizes and an ensemble of random structures, which we want to\ndesign. We find that for two letters almost none of these structures are\ndesignable. The designability improves for the three-letter case, but still a\nsignificant fraction of structures is undesignable. This changes when we look\nat the natural four-letter case with two pairs of complementary bases:\nundesignable structures are the exception, although they still exist. Finally,\nwe also study the relation between designability and the algorithmic complexity\nof the branch-and-bound algorithm. Within the ensemble of structures, a high\naverage degree of undesignability is correlated to a long time to prove that a\ngiven structure is (un-)designable. In the four-letter case, where the\ndesignability is high everywhere, the algorithmic complexity is highest in the\nregion of naturally occurring RNA.",
"arxiv_id": "physics/0609135",
"authors": [
"Bernd Burghardt",
"Alexander K. Hartmann"
],
"categories": [
"physics.bio-ph",
"q-bio.BM"
],
"doi": "10.1103/PhysRevE.75.021920",
"title": "RNA secondary structure design",
"url": "https://arxiv.org/abs/physics/0609135"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "866e2b8d-f300-4b81-81e8-21f0dd5053e8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}