Approximating the set of local minima in partial RNA folding landscapes

Article

Sahoo, S. and Albrecht, A. 2012. Approximating the set of local minima in partial RNA folding landscapes. Bioinformatics. 28 (4), pp. 523-530. https://doi.org/10.1093/bioinformatics/btr715
TypeArticle
TitleApproximating the set of local minima in partial RNA folding landscapes
AuthorsSahoo, S. and Albrecht, A.
Abstract

Motivation: We study a stochastic method for approximating the set of local minima in partial RNA folding landscapes associated with a bounded-distance neighbourhood of folding conformations. The conformations are limited to RNA secondary structures without pseudoknots. The method aims at exploring partial energy landscapes pL induced by folding simulations and their underlying neighbourhood relations. It combines an approximation of the number of local optima devised by Garnier and Kallel (2002) with a run-time estimation for identifying sets of local optima established by Reeves and Eremeev (2004).
Results: The method is tested on nine sequences of length between 50 nt and 400 nt, which allows us to compare the results with data generated by RNAsubopt and subsequent barrier tree calculations. On the nine sequences, the method captures on average 92% of local minima with settings designed for a target of 95%. The run-time of the heuristic can be estimated by O(n2Dνlnν), where n is the sequence length, ν is the number of local minima in the partial landscape pL under consideration and D is the maximum number of steepest descent steps in attraction basins associated with pL.

PublisherOxford University Press (OUP)
JournalBioinformatics
ISSN1367-4803
Publication dates
Print15 Feb 2012
Publication process dates
Deposited03 Jul 2013
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1093/bioinformatics/btr715
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/8428v

Log in to edit
  • 17
    total views
  • 0
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Long non-coding RNA structure and function: Is there a link? [Corrigendum]
Zampetaki, A., Albrecht, A. and Steinhofel, K. 2019. Long non-coding RNA structure and function: Is there a link? [Corrigendum]. Frontiers in Physiology, Frontiers Research Foundation. https://doi.org/10.3389/fphys.2019.01127
Long non-coding RNA structure and function: Is there a link?
Zampetaki, A., Albrecht, A. and Steinhofel, K. 2018. Long non-coding RNA structure and function: Is there a link? Frontiers in Physiology. 9. https://doi.org/10.3389/fphys.2018.01201
Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered miRNA processing
Lataniotis, L., Albrecht, A., Kok, F., Monfries, C., Benedetti, L., Lawson, N., Hughes, S., Steinhofel, K., Mayr, M. and Zampetaki, A. 2018. Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered miRNA processing. Cardiovascular Research. 114 (Supp_1), pp. S1-S1. https://doi.org/10.1093/cvr/cvy060
Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered mirna processing
Lataniotis, L., Albrecht, A., Kok, F., Monfries, C., Benedetti, L., Lawson, N., Hughes, S., Steinhofel, K., Mayr, M. and Zampetaki, A. 2017. Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered mirna processing. Heart. 103 (5), p. A133. https://doi.org/10.1136/heartjnl-2017-311726.193
Crispr/Cas9 editing reveals novel mechanisms of clustered microRNA regulation and function
Lataniotis, L., Albrecht, A., Kok, F., Monfries, C., Benedetti, L., Lawson, N., Hughes, S., Steinhofel, K., Mayr, M. and Zampetaki, A. 2017. Crispr/Cas9 editing reveals novel mechanisms of clustered microRNA regulation and function. Scientific Reports. 7, pp. 1-14. https://doi.org/10.1038/s41598-017-09268-0
Random versus deterministic descent in RNA energy landscape analysis
Day, L., Souki, O., Albrecht, A. and Steinhofel, K. 2016. Random versus deterministic descent in RNA energy landscape analysis. Advances in Bioinformatics. 2016. https://doi.org/10.1155/2016/9654921
A new heuristic method for approximating the number of local minima in partial RNA energy landscapes
Albrecht, A., Day, L., Souki, O. and Steinhofel, K. 2016. A new heuristic method for approximating the number of local minima in partial RNA energy landscapes. Computational Biology and Chemistry. 60, pp. 43-52. https://doi.org/10.1016/j.compbiolchem.2015.11.002
iRDA: a new filter towards predictive, stable, and enriched candidate genes
Lai, H., Albrecht, A. and Steinhofel, K. 2015. iRDA: a new filter towards predictive, stable, and enriched candidate genes. BMC Genomics. 16. https://doi.org/10.1186/s12864-015-2129-5
Robust signature discovery for affymetrix GeneChip® cancer classification
Lai, H., Albrecht, A. and Steinhofel, K. 2015. Robust signature discovery for affymetrix GeneChip® cancer classification. 6th International Conference on Agents and Artificial Intelligence. Angers, France 06 - 08 Mar 2014 Springer. pp. 329-345 https://doi.org/10.1007/978-3-319-25210-0_20
A new vision of evaluating gene expression signatures
Lai, H., Otzturk, C., Albrecht, A. and Steinhofel, K. 2015. A new vision of evaluating gene expression signatures. Computational Biology and Chemistry. 57, pp. 54-60. https://doi.org/10.1016/j.compbiolchem.2015.02.004
MicroRNA target prediction based upon metastable RNA secondary structures
Souki, O., Day, L., Albrecht, A. and Steinhofel, K. 2015. MicroRNA target prediction based upon metastable RNA secondary structures. 3rd International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO 2015). Granada, Spain 15 - 17 Apr 2015 Springer. pp. 456-467 https://doi.org/10.1007/978-3-319-16480-9_45
A framework for high-throughput gene signatures with microarray-based brain cancer gene expression profiling data
Lai, H., Albrecht, A. and Steinhöfel, K. 2014. A framework for high-throughput gene signatures with microarray-based brain cancer gene expression profiling data. 6th International Conference on Agents and Artificial Intelligence. Angers, France SCITEPRESS - Science and Technology Publications. https://doi.org/10.5220/0004926002110220
Energy-efficient multicast routing by using genetic local search
Katerinchuk, V., Albrecht, A. and Steinhofel, K. 2014. Energy-efficient multicast routing by using genetic local search. 6th International Conference on Agents and Artificial Intelligence. Angers, France 06 - 08 Mar 2014 pp. 740-746
Accessibility of microRNA binding sites in meta-stable RNA secondary structures in the presence of SNPs
Day, L., Abdelhadi Ep Souki, O., Albrecht, A. and Steinhofel, K. 2014. Accessibility of microRNA binding sites in meta-stable RNA secondary structures in the presence of SNPs. Bioinformatics. 30 (3), pp. 343-352. https://doi.org/10.1093/bioinformatics/btt695
A firefly-inspired method for protein structure prediction in lattice models
Maher, B., Albrecht, A., Loomes, M., Yang, X. and Steinhofel, K. 2014. A firefly-inspired method for protein structure prediction in lattice models. Biomolecules. 4 (1), pp. 56-75. https://doi.org/10.3390/biom4010056
Optimal placements of flexible objects. I. Analytical results for the unbounded case
Albrecht, A., Cheung, S., Hui, K., Leung, K. and Wong, C. 1997. Optimal placements of flexible objects. I. Analytical results for the unbounded case. IEEE Transactions on Computers. 46 (8), pp. 890-904. https://doi.org/10.1109/12.609278
Optimal placements of flexible objects. II. A simulated annealing approach for the bounded case
Albrecht, A., Cheung, S., Hui, K., Leung, K. and Wong, C. 1997. Optimal placements of flexible objects. II. A simulated annealing approach for the bounded case. IEEE Transactions on Computers. 46 (8), pp. 905-929. https://doi.org/10.1109/12.609279
The Steiner tree problem in orientation metrics
Yan, G., Albrecht, A., Young, G. and Wong, C. 1997. The Steiner tree problem in orientation metrics. Journal of Computer and System Sciences. 55 (3), pp. 529-546. https://doi.org/10.1006/jcss.1997.1513
Stochastic simulations of two-dimensional composite packings
Albrecht, A., Cheung, S., Leung, K. and Wong, C. 1997. Stochastic simulations of two-dimensional composite packings. Journal of Computational Physics. 136 (2), pp. 559-579. https://doi.org/10.1006/jcph.1997.5781
Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing
Albrecht, A., Cheung, S., Leung, K. and Wong, C. 1997. Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing. Mathematics and Computers in Simulation. 44 (2), pp. 187-215. https://doi.org/10.1016/S0378-4754(97)00072-4
Two simulated annealing-based heuristics for the job shop scheduling problem
Steinhofel, K., Albrecht, A. and Wong, C. 1999. Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operational Research. 118 (3), pp. 524-548. https://doi.org/10.1016/S0377-2217(98)00326-9
Logarithmic simulated annealing for X-ray diagnosis
Albrecht, A., Steinhofel, K., Taupitz, M. and Wong, C. 2001. Logarithmic simulated annealing for X-ray diagnosis. Artificial Intelligence in Medicine. 22 (3), pp. 249-260. https://doi.org/10.1016/S0933-3657(00)00112-3
Combining the perceptron algorithm with logarithmic simulated annealing
Albrecht, A. and Wong, C. 2001. Combining the perceptron algorithm with logarithmic simulated annealing. Neural Processing Letters. 14 (1), pp. 75-83. https://doi.org/10.1023/A:1011369322571
Fast parallel heuristics for the job shop scheduling problem
Steinhofel, K., Albrecht, A. and Wong, C. 2002. Fast parallel heuristics for the job shop scheduling problem. Computers and Operations Research. 29 (2), pp. 151-169. https://doi.org/10.1016/S0305-0548(00)00063-0
Bounded-depth threshold circuits for computer-assisted CT image classification
Albrecht, A., Hein, E., Steinhofel, K., Taupitz, M. and Wong, C. 2002. Bounded-depth threshold circuits for computer-assisted CT image classification. Artificial Intelligence in Medicine. 24 (2), pp. 179-192. https://doi.org/10.1016/S0933-3657(01)00101-4
The convergence of stochastic algorithms solving flow shop scheduling
Steinhofel, K., Albrecht, A. and Wong, C. 2002. The convergence of stochastic algorithms solving flow shop scheduling. Theoretical Computer Science. 285 (1), pp. 101-117. https://doi.org/10.1016/S0304-3975(01)00293-6
An experimental analysis of local minima to improve neighbourhood search
Steinhofel, K., Albrecht, A. and Wong, C. 2003. An experimental analysis of local minima to improve neighbourhood search. Computers and Operations Research. 30 (14), pp. 2157-2173. https://doi.org/10.1016/S0305-0548(02)00128-4
An Epicurean learning approach to gene-expression data classification
Albrecht, A., Vinterbo, S. and Ohno-Machado, L. 2003. An Epicurean learning approach to gene-expression data classification. Artificial Intelligence in Medicine. 28 (1), pp. 75-87. https://doi.org/10.1016/S0933-3657(03)00036-8
Classification improvement by an extended depth LSA machine
Albrecht, A. and Lappas, G. 2004. Classification improvement by an extended depth LSA machine. WSEAS Transactions on Systems. 3 (3), pp. 1120-1125.
On the evaluation of dividing samples for training an extended depth LSA machine
Albrecht, A. and Lappas, G. 2004. On the evaluation of dividing samples for training an extended depth LSA machine. WSEAS Transactions on Systems. 3 (3), pp. 1251-1257.
Gene selection guided by feature interdependence
Lai, H., Albrecht, A. and Steinhofel, K. 2013. Gene selection guided by feature interdependence. World Academy of Science, Engineering and Technology (WASET).
Derivative scores from site accessibility and ranking of miRNA target predictions
Dayem Ullah, A., Sahoo, S., Steinhofel, K. and Albrecht, A. 2012. Derivative scores from site accessibility and ranking of miRNA target predictions. International Journal of Bioinformatics Research and Applications. 8 (3/4), pp. 171-191. https://doi.org/10.1504/IJBRA.2012.048966
Ranking of microRNA target prediction scores by Pareto front analysis
Sahoo, S. and Albrecht, A. 2010. Ranking of microRNA target prediction scores by Pareto front analysis. Computational Biology and Chemistry. 34 (5-6), pp. 284-292. https://doi.org/10.1016/j.compbiolchem.2010.09.005
A note on a priori estimations of classification circuit complexity
Albrecht, A., Chashkin, A., Iliopoulos, C., Kasim-Zade, O., Lappas, G. and Steinhofel, K. 2010. A note on a priori estimations of classification circuit complexity. Fundamenta Informaticae. 104 (3), pp. 201-217. https://doi.org/10.3233/FI-2010-344
Uphill unfolding of native protein conformations in cubic lattices
Albrecht, A., Kapsokalivas, L. and Steinhofel, K. 2010. Uphill unfolding of native protein conformations in cubic lattices. Journal of Computational Science. 1 (1), pp. 6-12. https://doi.org/10.1016/j.jocs.2010.01.001
Analysis of local search landscapes for k-SAT instances
Albrecht, A., Lane, P. and Steinhofel, K. 2010. Analysis of local search landscapes for k-SAT instances. Mathematics in Computer Science. 3 (4), pp. 465-488. https://doi.org/10.1007/s11786-010-0040-7
Relating time complexity of protein folding simulation to approximations of folding time
Steinhofel, K., Skaliotis, A. and Albrecht, A. 2007. Relating time complexity of protein folding simulation to approximations of folding time. Computer Physics Communications. 176 (7), pp. 465-470. https://doi.org/10.1016/j.cpc.2006.12.002
Stochastic local search for the Feature Set problem, with applications to microarray data
Albrecht, A. 2006. Stochastic local search for the Feature Set problem, with applications to microarray data. Applied Mathematics and Computation. 183 (2), pp. 1148-1164. https://doi.org/10.1016/j.amc.2006.05.128
A stopping criterion for logarithmic simulated annealing
Albrecht, A. 2006. A stopping criterion for logarithmic simulated annealing. Computing. 78 (1), pp. 55-79. https://doi.org/10.1007/s00607-006-0167-1
A computational study on circuit size versus circuit depth
Lappas, G., Frank, R. and Albrecht, A. 2006. A computational study on circuit size versus circuit depth. International Journal on Artificial Intelligence Tools. 15 (2), pp. 143-162. https://doi.org/10.1142/S0218213006002606
Computer-assisted diagnosis of focal liver lesions on CT images: evaluation of the perceptron algorithm
Hein, E., Albrecht, A., Melzer, D., Steinhofel, K., Rogalla, P., Hamm, B. and Taupitz, M. 2005. Computer-assisted diagnosis of focal liver lesions on CT images: evaluation of the perceptron algorithm. Academic Radiology. 12 (9), pp. 1205 -1210. https://doi.org/10.1016/j.acra.2005.05.009
Stochastic protein folding simulation in the three-dimensional HP-model
Albrecht, A., Skaliotis, A. and Steinhöfel, K. 2008. Stochastic protein folding simulation in the three-dimensional HP-model. Computational Biology and Chemistry. 32 (4), pp. 248-255. https://doi.org/10.1016/j.compbiolchem.2008.03.004
Population-based local search for protein folding simulation in the MJ energy model and cubic lattices
Kapsokalivas, L., Gan, X., Albrecht, A. and Steinhöfel, K. 2009. Population-based local search for protein folding simulation in the MJ energy model and cubic lattices. Computational Biology and Chemistry. 33 (4), pp. 283-294. https://doi.org/10.1016/j.compbiolchem.2009.06.006
Combinatorial landscape analysis for k-SAT instances
Albrecht, A., Lane, P. and Steinhofel, K. 2008. Combinatorial landscape analysis for k-SAT instances. in: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence) IEEE. pp. 2498-2504
A local search heuristic for bounded-degree minimum spanning trees
Zahrani, M., Loomes, M., Malcolm, J. and Albrecht, A. 2008. A local search heuristic for bounded-degree minimum spanning trees. Engineering Optimization. 40 (12), pp. 1115-1135. https://doi.org/10.1080/03052150802317440
Adaptive simulated annealing for CT image classification
Loomes, M., Albrecht, A., Steinhoefel, K. and Taupitz, M. 2002. Adaptive simulated annealing for CT image classification. International Journal of Pattern Recognition and Artificial Intelligence. 16 (5), pp. 573-588.
Landscape analysis for multicast routing
Loomes, M., Albrecht, A., Malcolm, J. and Zahrani, M. 2006. Landscape analysis for multicast routing. Computer Communications. 30 (1), pp. 101-116. https://doi.org/10.1016/j.comcom.2006.07.019
Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing
Zahrani, M., Loomes, M., Malcolm, J., Ullah, A., Steinhoefel, K. and Albrecht, A. 2008. Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing. Computers and Operations Research. 35 (6), pp. 2049-2070. https://doi.org/10.1016/j.cor.2006.10.001