Delta: A Toolset for the Structural Analysis of Biological Sequences on a 3D Triangular Lattice

1. Abrahams, J.P., et al.: Prediction of RNA secondary structure, including pseudoknotting, by computer simulation. Nucleic Acids Research 18(10), 3035–3044 (1990)

   Article  Google Scholar 

2. Agarwala, R., et al.: Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97), pp. 390–399 (1997)

   Google Scholar 

3. Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics 104(1-3), 45–62 (2000)

   Article  MathSciNet  MATH  Google Scholar 

4. van Batenburg, F.H.D., Gultyaev, A.P., Pleij, C.W.A.: An APL-programmed genetic algorithm for the prediction of RNA secondary structure. Journal of Theoretical Biology 174(3), 269–280 (1995)

   Article  Google Scholar 

5. van Batenburg, F.H.D., et al.: Pseudobase: a database with RNA pseudoknots. Nucleic Acids Research 28(1), 201–204 (2000)

   Article  Google Scholar 

6. Berger, B., Leighton, T.: Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. In: Proceedings of the 2nd Conference on Computational Molecular Biology (RECOMB’98), pp. 30–39 (1998)

   Google Scholar 

7. Crescenzi, P., et al.: On the complexity of protein folding. In: Proceedings of the 2nd Conference on Computational Molecular Biology (RECOMB’98), pp. 61–62 (1998) and in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC’98), pp. 597–603 (1998)

   Google Scholar 

8. Crochemore, M., et al.: Approximating the 2-interval pattern problem. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 426–437. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

9. Deogun, J.S., et al.: RNA secondary structure prediction with simple pseudoknots. In: Proceedings of the 2nd Asia-Pacific Bioinformatics Conference (APBC’04), pp. 239–246 (2004)

   Google Scholar 

10. Dill, K.A.: Theory for the folding and stability of globular proteins. Biochemistry 24(6), 1501–1509 (1985)

    Article  Google Scholar 

11. Dill, K.A.: Dominant forces in protein folding. Biochemistry 29, 7133–7155 (1990)

    Article  Google Scholar 

12. Eddy, S.R.: How do RNA folding algorithms work? Nature Biotechnology 22(11), 1457–1458 (2004)

    Article  Google Scholar 

13. Gultyaev, A.P., van Batenburg, F.H.D., Pleij, C.W.A.: The computer simulation of RNA folding pathways using a genetic algorithm. Journal of Molecular Biology 250(1), 37–51 (1995)

    Article  Google Scholar 

14. Hart, W.E., Istrail, S.: Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal. In: Proc. 27th Annual ACM Symposium on Theory of Computing (STOC’95), pp. 157–168 (1995)

    Google Scholar 

15. Hofacker, I.L., et al.: Fast folding and comparison of RNA secondary structures. Monatshefte für Chemie 125(2), 167–188 (1994)

    Article  Google Scholar 

16. Ieong, S., et al.: Predicting RNA secondary structure with arbitrary pseudoknots by maximizing the number of stacking pairs. Journal of Computational Biology 10(6), 981–995 (2003)

    Article  Google Scholar 

17. Jiang, M.: A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem. Journal of Combinatorial Optimization, Special Issue on Bioinformatics, to appear

    Google Scholar 

18. Jiang, M.: Improved approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 399–410. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

19. Jiang, M., Zhu, B.: Protein folding on the hexagonal lattice in the HP model. Journal of Bioinformatics and Computational Biology 3(1), 19–34 (2005)

    Article  MathSciNet  Google Scholar 

20. Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  Google Scholar 

21. Lesh, N., Mitzenmacher, M., Whiteslides, S.: A complete and effective move set for simplified protein folding. In: Proceedings of the 7th Annual International Conference on Computational Molecular Biology (RECOMB’03), pp. 188–195 (2003)

    Google Scholar 

22. Lyngsø, R.B.: Complexity of pseudoknot prediction in simple models. In: Díaz, J., et al. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 919–931. Springer, Heidelberg (2004)

    Google Scholar 

23. Lyngsø, R.B., Pedersen, C.N.S.: RNA pseudoknot prediction in energy-based models. Journal of Computational Biology 7(3-4), 409–427 (2000)

    Article  Google Scholar 

24. Lyngsø, R.B., Zuker, M., Pedersen, C.N.S.: Fast evaluation of interval loops in RNA secondary structure prediction. Bioinformatics 15(6), 440–445 (1999)

    Article  Google Scholar 

25. Mauri, G., Pavesi, G., Piccolboni, A.: Approximation algorithms for protein folding prediction. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’99), pp. 945–946 (1999)

    Google Scholar 

26. Newman, A.: A new algorithm for protein folding in the HP model. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02), pp. 876–884 (2002)

    Google Scholar 

27. Nussinov, R., et al.: Algorithms for loop matching. SIAM Journal on Applied Mathematics 35(1), 68–82 (1978)

    Article  MathSciNet  MATH  Google Scholar 

28. Rivas, E., Eddy, S.R.: A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology 285, 2053–2068 (1999)

    Article  Google Scholar 

29. Ruan, J., Stormo, G.D., Zhang, W.: An iterated loop matching approach to the prediction of RNA secondary structure with pseudoknots. Bioinformatics 20(1), 58–66 (2004)

    Article  Google Scholar 

30. Shapiro, B.A., Wu, J.C.: Predicting RNA H-type pseudoknots with the massively parallel genetic algorithm. Computer Applications in the Biosciences 13(4), 459–471 (1997)

    Google Scholar 

31. Tabaska, J.E., et al.: An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics 14(8), 691–699 (1998)

    Article  Google Scholar 

32. Tinoco, I., et al.: Improved estimation of secondary structure in ribonucleic acids. Nature New Biology 246, 40–42 (1973)

    Google Scholar 

33. Uemura, Y., et al.: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science 210(2), 277–303 (1999)

    Article  MathSciNet  MATH  Google Scholar 

34. Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theoretical Computer Science 312, 223–249 (2004)

    Article  MathSciNet  MATH  Google Scholar 

35. Waterman, M.S.: Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman and Hall, Boca Raton (1995)

    MATH  Google Scholar 

36. Zuker, M., Stiegler, P.: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research 9(1), 133–148 (1981)

    Article  Google Scholar 

Download references