The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
Abstract
The alignment of finite sequences, the inference of ribonucleic acid secondary structures (folding), and the reconstruction of ancestral sequences on a phylogenetic tree, are three problems which have dynamic programming solutions, which we formulate in a common mathematical framework. Combining the objective functions for alignment (parsimony, or minimal mutations) and folding (free energy), we present an algorithm which solves all three problems simultaneously for a set of N sequences of length n in time proportional to $n^{3N} $ and storage $n^{2N} $. Incorporating a “cutting corners” constraint against biologically unlikely alignments reduces these requirements so that they are proportional to $n^{3} $ and $n^{2} $, respectively, for fixed N.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288
Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information
Zuker, M., & Stiegler, P. (1981) · Nucleic Acids Research · doi:10.1093/nar/9.1.133 · Cited by 3,562
Improved Estimation of Secondary Structure in Ribonucleic Acids
TINOCO, I., BORER, P. N., DENGLER, B., LEVINE, M. D., UHLENBECK, O. C., CROTHERS, D. M., & GRALLA, J. (1973) · Nature New Biology · doi:10.1038/newbio246040a0 · Cited by 2,268
Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison
Sankoff, D., & Kruskal, J. B. (1983) · Medical Entomology and Zoology · Cited by 1,915
Self-citationNussinov, R., Pieczenik, G., Griggs, J. R., & Kleitman, D. J. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135006 · Cited by 587
Minimal Mutation Trees of Sequences
Sankoff, D. (1975) · SIAM Journal on Applied Mathematics · doi:10.1137/0128004 · Cited by 575
Self-citationRNA secondary structures and their prediction
Zuker, M., & Sankoff, D. (1984) · Bulletin of Mathematical Biology · doi:10.1007/bf02459506 · Cited by 511
Self-citationOn the Theory and Computation of Evolutionary Distances
Sellers, P. H. (1974) · SIAM Journal on Applied Mathematics · doi:10.1137/0126070 · Cited by 474
Globin mRNA Sequences: Analysis of Base Pairing and Evolutionary Implications
Salser, W. (1978) · Cold Spring Harbor Symposia on Quantitative Biology · doi:10.1101/sqb.1978.042.01.099 · Cited by 398
Matching Sequences under Deletion/Insertion Constraints
Sankoff, D. (1972) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.69.1.4 · Cited by 296
Self-citation
Cited by
Lorenz, R., Bernhart, S. H., Höner zu Siederdissen, C., Tafer, H., Flamm, C., Stadler, P. F., & Hofacker, I. L. (2011) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-6-26 · Cited by 5,098
Recent developments in the MAFFT multiple sequence alignment program
Katoh, K., & Toh, H. (2008) · Briefings in Bioinformatics · doi:10.1093/bib/bbn013 · Cited by 3,586
Gruber, A. R., Lorenz, R., Bernhart, S. H., Neubock, R., & Hofacker, I. L. (2008) · Nucleic Acids Research · doi:10.1093/nar/gkn188 · Cited by 2,688
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
The equilibrium partition function and base pair binding probabilities for RNA secondary structure
McCaskill, J. S. (1990) · Biopolymers · doi:10.1002/bip.360290621 · Cited by 1,310
Rivas, E., & Eddy, S. R. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1998.2436 · Cited by 754
Secondary Structure Prediction for Aligned RNA Sequences
Hofacker, I. L., Fekete, M., & Stadler, P. F. (2002) · Journal of Molecular Biology · doi:10.1016/s0022-2836(02)00308-x · Cited by 639
RNAalifold: improved consensus structure prediction for RNA alignments
Bernhart, S. H., Hofacker, I. L., Will, S., Gruber, A. R., & Stadler, P. F. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-474 · Cited by 595
RNA secondary structures and their prediction
Zuker, M., & Sankoff, D. (1984) · Bulletin of Mathematical Biology · doi:10.1007/bf02459506 · Cited by 511
Self-citationInferring Noncoding RNA Families and Classes by Means of Genome-Scale Structure-Based Clustering
Will, S., Reiche, K., Hofacker, I. L., Stadler, P. F., & Backofen, R. (2007) · PLoS Computational Biology · doi:10.1371/journal.pcbi.0030065 · Cited by 499
Noncoding RNA gene detection using comparative sequence analysis
Rivas, E., & Eddy, S. R. (2001) · BMC Bioinformatics · doi:10.1186/1471-2105-2-8 · Cited by 491
Prediction of RNA secondary structure by free energy minimization
Mathews, D. H., & Turner, D. H. (2006) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2006.05.010 · Cited by 405
Hidden Markov Models and their Applications in Biological Sequence Analysis
Yoon, B.-J. (2009) · Current Genomics · doi:10.2174/138920209789177575 · Cited by 400
LocARNA-P: Accurate boundary prediction and improved detection of structural RNAs
Will, S., Joshi, T., Hofacker, I. L., Stadler, P. F., & Backofen, R. (2012) · RNA · doi:10.1261/rna.029041.111 · Cited by 394
[20] Computer prediction of RNA structure
Zuker, M. (1989) · Methods in Enzymology · doi:10.1016/0076-6879(89)80106-5 · Cited by 388
Dynalign: an algorithm for finding the secondary structure common to two RNA sequences
Mathews, D. H., & Turner, D. H. (2002) · Journal of Molecular Biology · doi:10.1006/jmbi.2001.5351 · Cited by 372
CMfinder—a covariance model based RNA motif finding algorithm
Yao, Z., Weinberg, Z., & Ruzzo, W. L. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btk008 · Cited by 360
RNA Pseudoknot Prediction in Energy-Based Models
Lyngsø, R. B., & Pedersen, C. N. S. (2000) · Journal of Computational Biology · doi:10.1089/106652700750050862 · Cited by 359
A comprehensive comparison of comparative RNA structure prediction approaches
Gardner, P. P., & Giegerich, R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-140 · Cited by 352
Inferring Non-Coding RNA Families and Classes by Means of Genome-Scale Structure-Based Clustering
Will, S., Reiche, K., Hofacker, I. L., Stadler, P. F., & Backofen, R. (2005) · PLoS Computational Biology · doi:10.1371/journal.pcbi.0030065.eor · Cited by 322
Baird, S. D., Turcotte, M., Korneluk, R. G., & Holcik, M. (2006) · RNA · doi:10.1261/rna.157806 · Cited by 306
RNAshapes: an integrated RNA analysis package based on abstract shapes
Steffen, P., Voß, B., Rehmsmeier, M., Reeder, J., & Giegerich, R. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btk010 · Cited by 306
RNA secondary structure: physical and computational aspects
Higgs, P. G. (2000) · Quarterly Reviews of Biophysics · doi:10.1017/s0033583500003620 · Cited by 287
Dowell, R. D., & Eddy, S. R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-71 · Cited by 280
A benchmark of multiple sequence alignment programs upon structural RNAs
Gardner, P. P. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki541 · Cited by 273
RSEARCH: Finding homologs of single structured RNA sequences
Klein, R. J., & Eddy, S. R. (2003) · BMC Bioinformatics · doi:10.1186/1471-2105-4-44 · Cited by 270
Multiple sequence alignment modeling: Methods and applications
Chatzou, M., Magis, C., Chang, J.-M., Kemena, C., Bussotti, G., Erb, I., & Notredame, C. (2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbv099 · Cited by 229
Metadata
- Authors
- Sankoff, D.
- Venue
- SIAM Journal on Applied Mathematics
- Published
- 1985-10
- Volume
- 45
- Issue
- 5
- Pages
- 810-825
- ISSN
- 0036-1399 (ISSN-L)
- 1095-712X
- OpenAlex
- W2095145214
- Cited by
- 530
- References
- 16
- FWCI
- 0.29
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.