Accelerated probabilistic inference of RNA structure evolution View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2005-12

AUTHORS

Ian Holmes

ABSTRACT

BACKGROUND: Pairwise stochastic context-free grammars (Pair SCFGs) are powerful tools for evolutionary analysis of RNA, including simultaneous RNA sequence alignment and secondary structure prediction, but the associated algorithms are intensive in both CPU and memory usage. The same problem is faced by other RNA alignment-and-folding algorithms based on Sankoff's 1985 algorithm. It is therefore desirable to constrain such algorithms, by pre-processing the sequences and using this first pass to limit the range of structures and/or alignments that can be considered. RESULTS: We demonstrate how flexible classes of constraint can be imposed, greatly reducing the computational costs while maintaining a high quality of structural homology prediction. Any score-attributed context-free grammar (e.g. energy-based scoring schemes, or conditionally normalized Pair SCFGs) is amenable to this treatment. It is now possible to combine independent structural and alignment constraints of unprecedented general flexibility in Pair SCFG alignment algorithms. We outline several applications to the bioinformatics of RNA sequence and structure, including Waterman-Eggert N-best alignments and progressive multiple alignment. We evaluate the performance of the algorithm on test examples from the RFAM database. CONCLUSION: A program, Stemloc, that implements these algorithms for efficient RNA sequence alignment and structure prediction is available under the GNU General Public License. More... »

PAGES

73

Identifiers

URI

http://scigraph.springernature.com/pub.10.1186/1471-2105-6-73

DOI

http://dx.doi.org/10.1186/1471-2105-6-73

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1048566346

PUBMED

https://www.ncbi.nlm.nih.gov/pubmed/15790387


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Algorithms", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Base Sequence", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Computational Biology", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Computer Simulation", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Databases, Genetic", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Databases, Protein", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Models, Statistical", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Nucleic Acid Conformation", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Pattern Recognition, Automated", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Probability", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Protein Structure, Tertiary", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "RNA", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Sensitivity and Specificity", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Sequence Alignment", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Sequence Analysis, RNA", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Sequence Homology, Nucleic Acid", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Software", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Time Factors", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of California, Berkeley", 
          "id": "https://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Department of Bioengineering, University of California, 94720-1762, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Holmes", 
        "givenName": "Ian", 
        "id": "sg:person.01063071571.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063071571.30"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1093/bioinformatics/19.1.108", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002169125"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0885-2308(90)90022-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003279399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/16.7.583", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004196591"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/9.1.133", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004222010"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(91)90193-a", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005533416"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008324105", 
          "https://doi.org/10.1038/nature02107"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008324105", 
          "https://doi.org/10.1038/nature02107"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0959-437x(99)00022-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011321474"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(87)90478-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012440962"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkg006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016135999"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/279069.279102", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020320282"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/279069.279102", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020320282"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(81)90087-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024589839"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(59)90362-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024707923"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02874", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025532636", 
          "https://doi.org/10.1038/nature02874"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02874", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025532636", 
          "https://doi.org/10.1038/nature02874"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.0404193101", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025701691"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/15.6.446", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026832020"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/bip.360290621", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032289021"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/25.18.3724", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032298574"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-5-166", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034350341", 
          "https://doi.org/10.1186/1471-2105-5-166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/22.23.5112", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037174533"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/bth229", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040557822"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jmbi.2001.5351", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040713999"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-5-71", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041215737", 
          "https://doi.org/10.1186/1471-2105-5-71"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-5-71", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041215737", 
          "https://doi.org/10.1186/1471-2105-5-71"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02871", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043341870", 
          "https://doi.org/10.1038/nature02871"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02871", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043341870", 
          "https://doi.org/10.1038/nature02871"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1101/gr.2821705", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045219682"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/22.11.2079", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045652226"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-2-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046362248", 
          "https://doi.org/10.1186/1471-2105-2-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0092-8674(03)00391-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048727079"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-4-44", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048914023", 
          "https://doi.org/10.1186/1471-2105-4-44"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45123-4_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051935477", 
          "https://doi.org/10.1007/3-540-45123-4_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45123-4_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051935477", 
          "https://doi.org/10.1007/3-540-45123-4_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/5.2.151", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059413859"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/6.4.309", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059413968"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1956.1056813", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061645517"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0145048", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062840393"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1075024888", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1082984658", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1083181416", 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005-12", 
    "datePublishedReg": "2005-12-01", 
    "description": "BACKGROUND: Pairwise stochastic context-free grammars (Pair SCFGs) are powerful tools for evolutionary analysis of RNA, including simultaneous RNA sequence alignment and secondary structure prediction, but the associated algorithms are intensive in both CPU and memory usage. The same problem is faced by other RNA alignment-and-folding algorithms based on Sankoff's 1985 algorithm. It is therefore desirable to constrain such algorithms, by pre-processing the sequences and using this first pass to limit the range of structures and/or alignments that can be considered.\nRESULTS: We demonstrate how flexible classes of constraint can be imposed, greatly reducing the computational costs while maintaining a high quality of structural homology prediction. Any score-attributed context-free grammar (e.g. energy-based scoring schemes, or conditionally normalized Pair SCFGs) is amenable to this treatment. It is now possible to combine independent structural and alignment constraints of unprecedented general flexibility in Pair SCFG alignment algorithms. We outline several applications to the bioinformatics of RNA sequence and structure, including Waterman-Eggert N-best alignments and progressive multiple alignment. We evaluate the performance of the algorithm on test examples from the RFAM database.\nCONCLUSION: A program, Stemloc, that implements these algorithms for efficient RNA sequence alignment and structure prediction is available under the GNU General Public License.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1186/1471-2105-6-73", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1023786", 
        "issn": [
          "1471-2105"
        ], 
        "name": "BMC Bioinformatics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "6"
      }
    ], 
    "name": "Accelerated probabilistic inference of RNA structure evolution", 
    "pagination": "73", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e75cc4261e71b57010940a57af7bbc2b43713ea9f57a5630eb2590f3f6549064"
        ]
      }, 
      {
        "name": "pubmed_id", 
        "type": "PropertyValue", 
        "value": [
          "15790387"
        ]
      }, 
      {
        "name": "nlm_unique_id", 
        "type": "PropertyValue", 
        "value": [
          "100965194"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1186/1471-2105-6-73"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048566346"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1186/1471-2105-6-73", 
      "https://app.dimensions.ai/details/publication/pub.1048566346"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T14:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8660_00000551.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1186%2F1471-2105-6-73"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-6-73'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-6-73'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-6-73'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-6-73'


 

This table displays all metadata directly associated to this object as RDF triples.

253 TRIPLES      21 PREDICATES      83 URIs      39 LITERALS      27 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1186/1471-2105-6-73 schema:about N0d0b71239c6b42cebd75d2ff0ac37df6
2 N1305a925abfe462cb6c91b56a97278aa
3 N14eae0af209b47969f22bae271911ab3
4 N24c3d89f2f58459b83d506862703774f
5 N304236aca2084dcdab8ea3014ff72613
6 N30c77193428d4203add2a538dd015713
7 N92b14f7001244c3e93d9cdff6ad2b6d4
8 N988df633a4264ec88c07b5ee12b9dc54
9 Nb79c8cbf8e7d4409a4f2f2acbea142e9
10 Nc1e7fff1739b43368e39a67cdc193621
11 Nc386b33d998c440d92f3644693422c32
12 Nd20cee8c2a344137b49efbe99a61ba3f
13 Nd6403b19a6574d0ab2666708e98911f8
14 Nd9aeb4328f714c55bcf4aa79921710aa
15 Ndcca0478c7124a44acf3c879e73cceeb
16 Ndda7023f10f1490b97a7ea66bf252f58
17 Ne7b2de30e4bf4e15924a49a90f371626
18 Ne99371af5aa94a8fafd6d17ede99fe97
19 anzsrc-for:08
20 anzsrc-for:0802
21 schema:author Ne6752d05a4404728bff8cb6c3f3349dd
22 schema:citation sg:pub.10.1007/3-540-45123-4_6
23 sg:pub.10.1038/nature02107
24 sg:pub.10.1038/nature02871
25 sg:pub.10.1038/nature02874
26 sg:pub.10.1186/1471-2105-2-8
27 sg:pub.10.1186/1471-2105-4-44
28 sg:pub.10.1186/1471-2105-5-166
29 sg:pub.10.1186/1471-2105-5-71
30 https://app.dimensions.ai/details/publication/pub.1075024888
31 https://app.dimensions.ai/details/publication/pub.1082984658
32 https://app.dimensions.ai/details/publication/pub.1083181416
33 https://doi.org/10.1002/bip.360290621
34 https://doi.org/10.1006/jmbi.2001.5351
35 https://doi.org/10.1016/0022-2836(81)90087-5
36 https://doi.org/10.1016/0022-2836(87)90478-5
37 https://doi.org/10.1016/0022-2836(91)90193-a
38 https://doi.org/10.1016/0885-2308(90)90022-x
39 https://doi.org/10.1016/s0019-9958(59)90362-6
40 https://doi.org/10.1016/s0092-8674(03)00391-x
41 https://doi.org/10.1016/s0959-437x(99)00022-2
42 https://doi.org/10.1073/pnas.0404193101
43 https://doi.org/10.1093/bioinformatics/15.6.446
44 https://doi.org/10.1093/bioinformatics/16.7.583
45 https://doi.org/10.1093/bioinformatics/19.1.108
46 https://doi.org/10.1093/bioinformatics/5.2.151
47 https://doi.org/10.1093/bioinformatics/6.4.309
48 https://doi.org/10.1093/bioinformatics/bth229
49 https://doi.org/10.1093/nar/22.11.2079
50 https://doi.org/10.1093/nar/22.23.5112
51 https://doi.org/10.1093/nar/25.18.3724
52 https://doi.org/10.1093/nar/9.1.133
53 https://doi.org/10.1093/nar/gkg006
54 https://doi.org/10.1101/gr.2821705
55 https://doi.org/10.1109/tit.1956.1056813
56 https://doi.org/10.1137/0145048
57 https://doi.org/10.1145/279069.279102
58 schema:datePublished 2005-12
59 schema:datePublishedReg 2005-12-01
60 schema:description BACKGROUND: Pairwise stochastic context-free grammars (Pair SCFGs) are powerful tools for evolutionary analysis of RNA, including simultaneous RNA sequence alignment and secondary structure prediction, but the associated algorithms are intensive in both CPU and memory usage. The same problem is faced by other RNA alignment-and-folding algorithms based on Sankoff's 1985 algorithm. It is therefore desirable to constrain such algorithms, by pre-processing the sequences and using this first pass to limit the range of structures and/or alignments that can be considered. RESULTS: We demonstrate how flexible classes of constraint can be imposed, greatly reducing the computational costs while maintaining a high quality of structural homology prediction. Any score-attributed context-free grammar (e.g. energy-based scoring schemes, or conditionally normalized Pair SCFGs) is amenable to this treatment. It is now possible to combine independent structural and alignment constraints of unprecedented general flexibility in Pair SCFG alignment algorithms. We outline several applications to the bioinformatics of RNA sequence and structure, including Waterman-Eggert N-best alignments and progressive multiple alignment. We evaluate the performance of the algorithm on test examples from the RFAM database. CONCLUSION: A program, Stemloc, that implements these algorithms for efficient RNA sequence alignment and structure prediction is available under the GNU General Public License.
61 schema:genre research_article
62 schema:inLanguage en
63 schema:isAccessibleForFree true
64 schema:isPartOf N69f28712731a4f80b1f01a74a3d7ff92
65 Nccd49038adfe4ae28b2752ea71abca8e
66 sg:journal.1023786
67 schema:name Accelerated probabilistic inference of RNA structure evolution
68 schema:pagination 73
69 schema:productId N14fa65f25298495982a750f983606652
70 N5e68bf802edb423690d4db580df535a3
71 N6c33a913b478481db786bc3f4d27e93a
72 N6ee803a66adf45e4ba6a9dccf59ba740
73 N9210a79c8beb44f6bf1a46285d4fcdcb
74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048566346
75 https://doi.org/10.1186/1471-2105-6-73
76 schema:sdDatePublished 2019-04-10T14:17
77 schema:sdLicense https://scigraph.springernature.com/explorer/license/
78 schema:sdPublisher N583bb72f7e2b4b7c878344fa3759b155
79 schema:url http://link.springer.com/10.1186%2F1471-2105-6-73
80 sgo:license sg:explorer/license/
81 sgo:sdDataset articles
82 rdf:type schema:ScholarlyArticle
83 N0d0b71239c6b42cebd75d2ff0ac37df6 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
84 schema:name Nucleic Acid Conformation
85 rdf:type schema:DefinedTerm
86 N1305a925abfe462cb6c91b56a97278aa schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
87 schema:name Pattern Recognition, Automated
88 rdf:type schema:DefinedTerm
89 N14eae0af209b47969f22bae271911ab3 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
90 schema:name Sequence Homology, Nucleic Acid
91 rdf:type schema:DefinedTerm
92 N14fa65f25298495982a750f983606652 schema:name nlm_unique_id
93 schema:value 100965194
94 rdf:type schema:PropertyValue
95 N24c3d89f2f58459b83d506862703774f schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
96 schema:name Algorithms
97 rdf:type schema:DefinedTerm
98 N304236aca2084dcdab8ea3014ff72613 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
99 schema:name Databases, Genetic
100 rdf:type schema:DefinedTerm
101 N30c77193428d4203add2a538dd015713 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
102 schema:name Models, Statistical
103 rdf:type schema:DefinedTerm
104 N583bb72f7e2b4b7c878344fa3759b155 schema:name Springer Nature - SN SciGraph project
105 rdf:type schema:Organization
106 N5e68bf802edb423690d4db580df535a3 schema:name dimensions_id
107 schema:value pub.1048566346
108 rdf:type schema:PropertyValue
109 N69f28712731a4f80b1f01a74a3d7ff92 schema:issueNumber 1
110 rdf:type schema:PublicationIssue
111 N6c33a913b478481db786bc3f4d27e93a schema:name doi
112 schema:value 10.1186/1471-2105-6-73
113 rdf:type schema:PropertyValue
114 N6ee803a66adf45e4ba6a9dccf59ba740 schema:name pubmed_id
115 schema:value 15790387
116 rdf:type schema:PropertyValue
117 N9210a79c8beb44f6bf1a46285d4fcdcb schema:name readcube_id
118 schema:value e75cc4261e71b57010940a57af7bbc2b43713ea9f57a5630eb2590f3f6549064
119 rdf:type schema:PropertyValue
120 N92b14f7001244c3e93d9cdff6ad2b6d4 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
121 schema:name Computer Simulation
122 rdf:type schema:DefinedTerm
123 N988df633a4264ec88c07b5ee12b9dc54 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
124 schema:name Time Factors
125 rdf:type schema:DefinedTerm
126 Nb79c8cbf8e7d4409a4f2f2acbea142e9 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
127 schema:name Computational Biology
128 rdf:type schema:DefinedTerm
129 Nc1e7fff1739b43368e39a67cdc193621 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
130 schema:name Software
131 rdf:type schema:DefinedTerm
132 Nc386b33d998c440d92f3644693422c32 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
133 schema:name Protein Structure, Tertiary
134 rdf:type schema:DefinedTerm
135 Nccd49038adfe4ae28b2752ea71abca8e schema:volumeNumber 6
136 rdf:type schema:PublicationVolume
137 Nd20cee8c2a344137b49efbe99a61ba3f schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
138 schema:name Probability
139 rdf:type schema:DefinedTerm
140 Nd6403b19a6574d0ab2666708e98911f8 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
141 schema:name Sequence Alignment
142 rdf:type schema:DefinedTerm
143 Nd9aeb4328f714c55bcf4aa79921710aa schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
144 schema:name Databases, Protein
145 rdf:type schema:DefinedTerm
146 Ndcca0478c7124a44acf3c879e73cceeb schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
147 schema:name Sensitivity and Specificity
148 rdf:type schema:DefinedTerm
149 Ndda7023f10f1490b97a7ea66bf252f58 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
150 schema:name Sequence Analysis, RNA
151 rdf:type schema:DefinedTerm
152 Ne6752d05a4404728bff8cb6c3f3349dd rdf:first sg:person.01063071571.30
153 rdf:rest rdf:nil
154 Ne7b2de30e4bf4e15924a49a90f371626 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
155 schema:name Base Sequence
156 rdf:type schema:DefinedTerm
157 Ne99371af5aa94a8fafd6d17ede99fe97 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
158 schema:name RNA
159 rdf:type schema:DefinedTerm
160 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
161 schema:name Information and Computing Sciences
162 rdf:type schema:DefinedTerm
163 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
164 schema:name Computation Theory and Mathematics
165 rdf:type schema:DefinedTerm
166 sg:journal.1023786 schema:issn 1471-2105
167 schema:name BMC Bioinformatics
168 rdf:type schema:Periodical
169 sg:person.01063071571.30 schema:affiliation https://www.grid.ac/institutes/grid.47840.3f
170 schema:familyName Holmes
171 schema:givenName Ian
172 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063071571.30
173 rdf:type schema:Person
174 sg:pub.10.1007/3-540-45123-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051935477
175 https://doi.org/10.1007/3-540-45123-4_6
176 rdf:type schema:CreativeWork
177 sg:pub.10.1038/nature02107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008324105
178 https://doi.org/10.1038/nature02107
179 rdf:type schema:CreativeWork
180 sg:pub.10.1038/nature02871 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043341870
181 https://doi.org/10.1038/nature02871
182 rdf:type schema:CreativeWork
183 sg:pub.10.1038/nature02874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025532636
184 https://doi.org/10.1038/nature02874
185 rdf:type schema:CreativeWork
186 sg:pub.10.1186/1471-2105-2-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046362248
187 https://doi.org/10.1186/1471-2105-2-8
188 rdf:type schema:CreativeWork
189 sg:pub.10.1186/1471-2105-4-44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048914023
190 https://doi.org/10.1186/1471-2105-4-44
191 rdf:type schema:CreativeWork
192 sg:pub.10.1186/1471-2105-5-166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034350341
193 https://doi.org/10.1186/1471-2105-5-166
194 rdf:type schema:CreativeWork
195 sg:pub.10.1186/1471-2105-5-71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041215737
196 https://doi.org/10.1186/1471-2105-5-71
197 rdf:type schema:CreativeWork
198 https://app.dimensions.ai/details/publication/pub.1075024888 schema:CreativeWork
199 https://app.dimensions.ai/details/publication/pub.1082984658 schema:CreativeWork
200 https://app.dimensions.ai/details/publication/pub.1083181416 schema:CreativeWork
201 https://doi.org/10.1002/bip.360290621 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032289021
202 rdf:type schema:CreativeWork
203 https://doi.org/10.1006/jmbi.2001.5351 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040713999
204 rdf:type schema:CreativeWork
205 https://doi.org/10.1016/0022-2836(81)90087-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024589839
206 rdf:type schema:CreativeWork
207 https://doi.org/10.1016/0022-2836(87)90478-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012440962
208 rdf:type schema:CreativeWork
209 https://doi.org/10.1016/0022-2836(91)90193-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1005533416
210 rdf:type schema:CreativeWork
211 https://doi.org/10.1016/0885-2308(90)90022-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1003279399
212 rdf:type schema:CreativeWork
213 https://doi.org/10.1016/s0019-9958(59)90362-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024707923
214 rdf:type schema:CreativeWork
215 https://doi.org/10.1016/s0092-8674(03)00391-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048727079
216 rdf:type schema:CreativeWork
217 https://doi.org/10.1016/s0959-437x(99)00022-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011321474
218 rdf:type schema:CreativeWork
219 https://doi.org/10.1073/pnas.0404193101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025701691
220 rdf:type schema:CreativeWork
221 https://doi.org/10.1093/bioinformatics/15.6.446 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026832020
222 rdf:type schema:CreativeWork
223 https://doi.org/10.1093/bioinformatics/16.7.583 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004196591
224 rdf:type schema:CreativeWork
225 https://doi.org/10.1093/bioinformatics/19.1.108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002169125
226 rdf:type schema:CreativeWork
227 https://doi.org/10.1093/bioinformatics/5.2.151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059413859
228 rdf:type schema:CreativeWork
229 https://doi.org/10.1093/bioinformatics/6.4.309 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059413968
230 rdf:type schema:CreativeWork
231 https://doi.org/10.1093/bioinformatics/bth229 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040557822
232 rdf:type schema:CreativeWork
233 https://doi.org/10.1093/nar/22.11.2079 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045652226
234 rdf:type schema:CreativeWork
235 https://doi.org/10.1093/nar/22.23.5112 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037174533
236 rdf:type schema:CreativeWork
237 https://doi.org/10.1093/nar/25.18.3724 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032298574
238 rdf:type schema:CreativeWork
239 https://doi.org/10.1093/nar/9.1.133 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004222010
240 rdf:type schema:CreativeWork
241 https://doi.org/10.1093/nar/gkg006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016135999
242 rdf:type schema:CreativeWork
243 https://doi.org/10.1101/gr.2821705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045219682
244 rdf:type schema:CreativeWork
245 https://doi.org/10.1109/tit.1956.1056813 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061645517
246 rdf:type schema:CreativeWork
247 https://doi.org/10.1137/0145048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062840393
248 rdf:type schema:CreativeWork
249 https://doi.org/10.1145/279069.279102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020320282
250 rdf:type schema:CreativeWork
251 https://www.grid.ac/institutes/grid.47840.3f schema:alternateName University of California, Berkeley
252 schema:name Department of Bioengineering, University of California, 94720-1762, Berkeley, CA, USA
253 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...