A survey on syntactic patternrecognition methodsin bioinformatics

• Autorzy: Flasiński Mariusz

Identyfikatory

DOI

10.7494/csci.2024.25.1.6153

• Języki publikacji: EN

Abstrakty

EN

Formal tools and models of syntactic pattern recognition which are used inbioinformatics are introduced and characterized in the paper. They include,among others: stochastic (string) grammars and automata, hidden Markovmodels, programmed grammars, attributed grammars, stochastic tree grammars, Tree Adjoining Grammars (TAGs), algebraic dynamic programming, NLC- and NCE-type graph grammars, and algebraic graph transformation systems. The survey of applications of these formal tools and models in bioinfor-matics is presented.

Słowa kluczowe

EN

bioinformatics; syntactic pattern recognition; generative grammar; hiddenMarkov model (HMM); HMM

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2024
• Tom: T. 25 (1)
• Strony: 5--42
• Opis fizyczny: Bibliogr. 212 poz., rys., tab., wykr.

Twórcy

autor

Flasiński Mariusz

• Jagiellonian University, Information Technology Systems Department, Cracow 30-348, ul. prof. St. Lojasiewicza 4, Poland

Bibliografia

• [1] Abe N., Mamitsuka H.: Predicting protein secondary structure using stochastictree grammars,Machine Learning, vol. 29, pp. 275–301, 1997.
• [2] Agarwal S., Vaz C., Bhattacharya A., Srinivasan A.: Prediction of novel precur-sor miRNAs using a context-sensitive hidden Markov model (CSHMM),BMCBioinformatics, vol. 11 (Suppl 1): S29, 2010. doi: 10.1186/1471-2105-11-s1-s29.
• [3] Ahola V., Aittokallio T., Uusipaikka E., Vihinen M.: Efficient estimation ofemission probabilities in profile hidden Markov models,Bioinformatics, vol. 19,pp. 2359–2368, 2003. doi: 10.1093/bioinformatics/btg328.
• [4] Alves J.M.P., de Oliveira A.L., Sandberg T.O.M., Moreno-Gallego J.L.,de Toledo M.A.F., de Moura E.M.M., Oliveira L.S.,et al.: GenSeed-HMM:A tool for progressive assembly using profile HMMs as seeds and its applicationin alpavirinae viral discovery from metagenomic data,Frontiers in Microbiology,vol. 7, 269, 2016. doi: 10.3389/fmicb.2016.00269.
• [5] Anderson J.W.J., Tataru P., Staines J., Hein J., Lyngsø R.: Evolving stochasticcontext-free grammars for RNA secondary structure prediction,BMC Bioinfor-matics, vol. 13, 78, 2012. doi: 10.1186/1471-2105-13-78.
• [6] Bagos P.G., Liakopoulos T.D., Hamodrakas S.J.: Evaluation of methods forpredicting the topology ofβ-barrel outer membrane proteins and a consensusprediction method,BMC Bioinformatics, vol. 6, 7, 2005. doi: 10.1186/1471-2105-6-7.
• [7] Bagos P.G., Liakopoulos T.D., Spyropoulos I.C., Hamodrakas S.J.: A hiddenMarkov model method, capable of predicting and discriminatingβ-barrel outermembrane proteins,BMC Bioinformatics, vol. 5, 29, 2004. doi: 10.1186/1471-2105-5-29.
• [8] Bagos P.G.,Liakopoulos T.D.,Spyropoulos I.C.,Hamodrakas S.J.:PRED-TMBB: a web server for predicting the topology ofβ-barrel outermembrane proteins,Nucleic Acids Research, vol. 32, pp. W400–W404, 2004.doi: 10.1093/nar/gkh417.
• [9] Baldi P., Brunak S.:Bioinformatics: The Machine Learning Approach, MITPress, Cambridge, MA, 2001.
• [10] Baldi P., Chauvin Y., Hunkapillar T., McClure M.: Hidden Markov models ofbiological primary sequence information,Proceedings of the National Academy ofSciences of the USA, vol. 91, pp. 1059–1063, 1994. doi: 10.1073/pnas.91.3.1059.
• [11] Baum L.E., Petrie T.: Statistical inference for probabilistic functions of fi-nite state Markov chains,The Annals of Mathematical Statistics, vol. 37,pp. 1554–1563, 1966. doi: 10.1214/aoms/1177699147.
• [12] Bellman R.:Dynamic Programming, Princeton University Press, Princeton, NJ,1957. doi: 10.2307/j.ctv1nxcw0f.
• [13] Bentolila S.: A grammar describing ‘biological binding operators’ to modelgene regulation,Biochimie, vol. 78, pp. 335–350, 1996. doi: 10.1016/0300-9084(96)84766-3.
• [14] Berkemer S.J., zu Siederdissen H ̈oner C., Stadler P.F.: Algebraic dynamic pro-gramming on trees,Algorithms, vol. 10, 135, 2017. doi: 10.3390/a10040135.
• [15] Bernardes J.S., D ́avila A.M.R., Costa V.S., Zaverucha G.: Improving modelconstruction of profile HMMs for remote homology detection through struc-tural alignment,BMC Bioinformatics, vol. 8, 435, 2007. doi: 10.1186/1471-2105-8-435.
• [16] Bhargava B.K., Fu K.: Stochastic tree systems for syntactic pattern recognition.In:Proceedings of Twelfth Annual Allerton Conference on Circuit and SystemTheory, pp. 278–287, Monticello, IL, 1974.
• [17] Booth T.L., Thompson R.A.: Applying probability measures to abstract lan-guages,IEEE Trans Computers, vol. 22, pp. 442–450, 1973. doi: 10.1109/t-c.1973.223746.
• [18] Brainerd W.S.: Tree generating regular systems,Information and Control,vol. 14, pp. 217–231, 1969. doi: 10.1016/s0019-9958(69)90065-5.
• [19] Bralley P.: An introduction to molecular linguistics,BioScience, vol. 46,pp. 146–153, 1996. doi: 10.2307/1312817.
• [20] Brandenburg F.J.: On the complexity of the membership problem of graphgrammars. In:Proceedings of the Workshop on Graphtheoretic Concepts in Com-puter Science, pp. 40–49, Osnabr ̈uck, Germany, 1983.
• [21] Brejov ́a B., Brown D.G., Vinaˇr T.: The most probable annotation problem inHMMs and its application to bioinformatics,Journal of Computer and SystemSciences, vol. 73, pp. 1060–1077, 2007. doi: 10.1016/j.jcss.2007.03.011.
• [22] Brendel V., Busse H.G.: Genome structure described by formal languages,Nu-cleic Acids Research, vol. 12, pp. 2561–2568, 1984.
• [23] Brown M., Wilson C.: RNA pseudoknot modeling using intersections of stochas-tic context free grammars with applications to database search. In:Proceedingsof 1996 Pacific Symposium on Biocomputing, pp. 109–125, Hawaii, 1996.
• [24] Brown M.P.: Small subunit ribosomal RNA modeling using stochastic context-free grammars. In:Proceedings of 8th Internatonal Conference on IntelligentSystems for Molecular Biology, pp. 57–66, San Diego, CA, USA, 2000.
• [25] Bunke H., Sanfeliu A. (eds.):Syntactic and Structural Pattern Recognition –Theory and Applications, World Scientific, Singapore, 1990. doi: 10.1142/0580.
• [26] Bystroff C., Krogh A.: Hidden Markov models for prediction of protein fea-tures. In: M. Zaki, C. Bystroff (eds.),Protein Structure Prediction. Meth-ods in Molecular Biology, pp. 173–198, Humana Press, New Jersey, 2008.doi: 10.1007/978-1-59745-574-97.
• [27] Bystroff C., Shao Y., Yuan X.: Five hierarchical levels of sequence-structurecorrelation in proteins,Applied Bioinformatics, vol. 3, pp. 97–104, 2004.doi: 10.2165/00822942-200403020-00004.
• [28] Cai L., Malmberg R., Wu Y.: Stochastic modeling of RNA pseudoknottedstructures: A grammatical approach,Bioinformatics, vol. 19, pp. i66–i73, 2003.doi: 10.1093/bioinformatics/btg1007.
• [29] Cai Y., Lux M.W., Adam L., Peccoud J.: Modeling structure-function relation-ships in synthetic DNA sequences using attribute grammars,PLoS Computa-tional Biology, vol. 5, e1000529, 2009. doi: 10.1371/journal.pcbi.1000529.
• [30] Chiang D., Joshi A.K., Searls D.B.: Grammatical representations of macro-molecular structure,Journal of Computational Biology, vol. 13, pp. 1077–1100,2006. doi: 10.1089/cmb.2006.13.1077.
• [31] Collado-Vides J.: A transformational-grammar approach to the study of the reg-ulation of gene expression,Journal of Theoretical Biology, vol. 136, pp. 403–425,1989. doi: 10.1016/s0022-5193(89)80156-0.
• [32] Collado-Vides J.: A syntactic representation of units of genetic information –A syntax of units of genetic information,Journal of Theoretical Biology,vol 148,pp. 401–429, 1991. doi: 10.1016/s0022-5193(05)80245-0.
• [33] Collado-Vides J.: Grammatical model of the regulation of gene expression,Pro-ceedings of the National Academy of Sciences of the United States of America,vol. 89, pp. 9405–9409, 1992. doi: 10.1073/pnas.89.20.9405.
• [34] Corn S.:Explicit definitions and linguistics dominoes. In:J.F. Hart,S. Takasu (eds.),Systems and Computer Science, University of Toronto Press,Toronto, 1967.
• [35] Coste F.: Learning the language of biological sequences. In: J. Heinz, J.M. Sem-pere (eds.),Topics in Grammatical Inference, pp. 215–247, Springer, 2016.doi: 10.1007/978-3-662-48395-48.
• [36] Datta S., Mukhopadhyay S.: A composite method based on formal grammarand DNA structural features in detecting human polymerase II promoter region,PLoS ONE, vol. 8, e54843, 2013. doi: 10.1371/journal.pone.0054843.
• [37] Dill K.E., Lucas A., Hockenmaier J., Huang L., Chiang D., Joshi A.K.: Com-putational linguistics: A new tool for exploring biopolymer structures andstatistical mechanics,Polymer, vol. 48, pp. 4289–4300, 2007. doi: 10.1016/j.polymer.2007.05.018.
• [38] Ding L., Samad A., Xue X., Huang X., Malmberg R.L., Cai L.: Stochastick-tree grammar and its application in biomolecular structure modeling,LectureNotes in Computer Science, vol. 8370, pp. 308–322, 2014. doi: 10.1007/978-3-319-04921-225.
• [39] Do C.B., Mahabhashyam M.S., Brudno M., Batzoglou S.: ProbCons: Prob-abilistic consistency-based multiple sequence alignment,Genome Research,vol. 15, pp. 330–340, 2005. doi: 10.1101/gr.2821705.
• [40] Do C.B., Woods D.A., Batzoglou S.: CONTRAfold: RNA secondary structureprediction without physics-based models,Bioinformatics, vol. 22, pp. e90–e98,2006. doi: 10.1093/bioinformatics/btl246.
• [41] Dong S., Searls D.B.: Gene structure prediction by linguistic methods,Ge-nomics, vol. 23, pp. 540–551, 1994. doi: 10.1006/geno.1994.1541.
• [42] Dowell R.D., Eddy S.R.: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction,BMC Bioinformatics,vol. 5, 71, 2004. doi: 10.1186/1471-2105-5-71.
• [43] Duda R.O., Hart P.E., Stork D.G.:Pattern Classification, Wiley, NewYork, 2001.
• [44] Durbin R., Eddy S.R., Krogh A., Mitchison G.:Biological Sequence Analysis:Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press,Cambridge, UK, 2002.
• [45] Dyrka W., Nebel J.C.: A stochastic context free grammar based frameworkfor analysis of protein sequences,BMC Bioinformatics, vol. 10, 323, 2009.doi: 10.1186/1471-2105-10-323.
• [46] Dyrka W., Nebel J.C., Kotulska M.: Probabilistic grammatical model of proteinlanguage and its application to helix-helix contact site classification,Algorithmsfor Molecular Biology, vol. 8, 31, 2013.
• [47] Eddy S.R.: Profile hidden Markov models,Bioinformatics, vol. 14, pp. 755–763,1998. doi: 10.1093/bioinformatics/14.9.755.
• [48] Eddy S.R.: What is a hidden Markov model?,Nature Biotechnology, vol. 22,pp. 1315–1316, 2004. doi: 10.1038/nbt1004-1315.
• [49] Eggers D., zu Siederdissen H ̈oner H.C., Stadler P.F.: Accuracy of RNA structureprediction depends on the pseudoknot grammar,Lecture Notes in ComputerScience, vol. 13523, pp. 20–31, 2022. doi: 10.1007/978-3-031-21175-13.
• [50] Ehrig H., Ehrig K., Prange U., Taentzer G.:Fundamentals of Algebraic GraphTransformation, Springer, Berlin-Heidelberg, 2006.
• [51] Ehrig H., Engels G., Kreowski H.J., Rozenberg G. (eds.):Handbook ofGraph Grammars and Computing by Graph Transformation, Vol. 2: Applica-tions, Languages and Tools, World Scientific, Singapore, 1999. doi: 10.1142/9789812815149.
• [52] Ehrig H., Kreowski H.J.: Pushout-properties: An analysis of gluing con-structions for graphs,Mathematische Nachrichten, vol. 91, pp. 135–149, 1979.doi: 10.1002/mana.19790910111.
• [53] Ehrig H., Pfender M., Schneider H.J.: Graph grammars: An algebraic approach.In:Proceedings of 14th Annual IEEE Symposium on Switching and AutomataTheory, pp. 167–180, 1973. doi: 10.1109/swat.1973.11.
• [54] Flasi ́nski M.: Parsing of edNLC-graph grammars for scene analysis,PatternRecognition, vol. 21, pp. 623–629, 1988. doi: 10.1016/0031-3203(88)90034-9.
• [55] Flasi ́nski M.: Distorted pattern analysis with the help of Node Label Controlledgraph languages,Pattern Recognition, vol. 23, pp. 765–774, 1990. doi: 10.1016/0031-3203(90)90099-7.
• [56] Flasi ́nski M.: On the parsing of deterministic graph languages for syntacticpattern recognition,Pattern Recognition, vol. 26, pp. 1–16, 1993. doi: 10.1016/0031-3203(93)90083-9.
• [57] Flasi ́nski M.: Use of graph grammars for the description of mechanical parts,Computer-Aided Design, vol. 27, pp. 403–433, 1995.doi: 10.1016 / 0010 -4485(94)00015-6.
• [58] Flasi ́nski M.: Power properties of NLC graph grammars with a polynomial mem-bership problem,Theoretical Computer Science, vol. 201, pp. 189–231, 1998.doi: 10.1016/s0304-3975(97)00212-0.
• [59] Flasi ́nski M.: Inference of parsable graph grammars for syntactic pattern recog-nition,Fundamenta Informaticae, vol. 80, pp. 379–413, 2007.
• [60] Flasi ́nski M.:Introduction to Artificial Intelligence, Springer International,Switzerland, 2016. doi: 10.1007/978-3-319-40022-8.
• [61] Flasi ́nski M.:Syntactic Pattern Recognition, World Scientific, New Jersey-London-Singapore, 2019.
• [62] Flasi ́nski M., Jurek J.: Dynamically programmed automata for quasi contextsensitive languages as a tool for inference support in pattern recognition-basedreal-time control expert systems,Pattern Recognition, vol. 32, pp. 671–690, 1999.doi: 10.1016/s0031-3203(98)00115-0.
• [63] Flasi ́nski M., Kotulski L.: On the use of graph grammars for the con-trol of a distributed software allocation,The Computer Journal, vol. 35,pp. A165–A175 1992.
• [64] Flasi ́nski M., Lewicki G.: The convergent method of constructing polynomialdiscriminant functions for pattern recognition,Pattern Recognition, vol. 24,pp. 1009–1015, 1991. doi: 10.1016/0031-3203(91)90098-p.
• [65] Flasi ́nski M., My ́sli ́nski S.: On the use of graph parsing for recognition ofisolated hand postures of Polish Sign Language,Pattern Recognition, vol. 43,pp. 2249–2264, 2010. doi: 10.1016/j.patcog.2010.01.004.
• [66] Flasi ́nski M., Jurek J., Peszek T.: Multi-derivational parsing of vague lan-guages – the new paradigm of syntactic pattern recognition,IEEE Transac-tions on Pattern Analysis and Machine Intelligence, vol. 46, 2024. doi: 10.1109/tpami.2024.3367245.
• [67] Fonzo de V., Aluffi-Pentini F., Parisi V.: Hidden Markov models in bioin-formatics,Current Bioinformatics, vol. 2, pp. 49–61, 2007.doi: 10.2174/157489307779314348.
• [68] Fu K.S.: Stochastic tree languages and their application to picture processing.In: P.R. Krishnaiah (ed.),Multivariate Analysis V, North-Holland, Amster-dam, 1980.
• [69] Fu K.S.: Stochastic automata, stochastic languages and pattern recognition,Journal of Cybernetics, vol. 1, pp. 31–49, 1971.
• [70] Fu K.S.:Syntactic Pattern Recognition and Applications, Prentice Hall, Engle-wood Cliffs, 1982.
• [71] Fu K.S., Huang T.: Stochastic grammars and languages,International Journalof Computer and Information Sciences, vol. 1, pp. 135–170, 1972. doi: 10.1007/bf00995736.
• [72] Fu K.S., Li T.: On stochastic automata and languages,Information Sciences,vol. 1, pp. 403–419, 1969. doi: 10.1016/0020-0255(69)90024-3.
• [73] Gallego A.J., L ́opez D., Calera-Rubio J.: Grammatical inference of directedacyclic graph languages with polynomial time complexity,Journal of Computerand System Sciences, vol. 95, pp. 19–34, 2018. doi: 10.1016/j.jcss.2017.12.002.
• [74] G ́ecseg F., Steinby M.:Tree Automata, Akad ́emiai Kiad ́o, Budapest, 1984.
• [75] Ghouila A., Florent I., Guerfali F.Z., Terrapon N., Laouini D., Yahia S.B.,Gascuel O.,et al.: Identification of Divergent Protein Domains by CombiningHMM-HMM Comparisons and Co-Occurrence Detection,PLoS ONE, vol. 9,e95275, 2014. doi: 10.1371/journal.pone.0095275.
• [76] Giegerich R.:A declarative approach to the development of dynamic program-ming algorithms, applied to RNA folding, Tech. rep., Bielefeld University, Ger-many, 1998.
• [77] Giegerich R.: Explaining and controlling ambiguity in dynamic programming,Lecture Notes in Computer Science, vol. 1848, pp. 46–59, 2000. doi: 10.1007/3-540-45123-46.
• [78] Giegerich R.: A systematic approach to dynamic programming in bioinformatics,Bioinformatics, vol. 16(8), pp. 665–677, 2000. doi: 10.1093/bioinformatics/16.8.665.
• [79] Giegerich R., Meyer C.: Algebraic Dynamic Programming,Lecture Notes inComputer Science, vol. 2422, pp. 349–364, 2002. doi: 10.1007/3-540-45719-424.
• [80] Giegerich R., Touzet H.: Modeling dynamic programming problems over se-quences and trees with inverse coupled rewrite systems,Algorithms, vol. 7,pp. 62–144, 2014. doi: 10.3390/a7010062.
• [81] Giegerich R., Meyer C., Steffen P.: Towards a discipline of dynamic program-ming,Lecture Notes in Informatics, vol. P-147, pp. 3–44, 2002.
• [82] Giegerich R., Meyer C., Steffen P.: A discipline of dynamic programming oversequence data,Science of Computer Programming, vol. 51, pp. 215–263, 2004.doi: 10.1016/j.scico.2003.12.005.
• [83] Golab T., Ledley R.S., Rotolo L.S.: FIDAC: Film input to digital automaticcomputer,Pattern Recognition, vol. 3, pp. 123–156, 1971. doi: 10.1016/0031-3203(71)90035-5.
• [84] Gollery M. (ed.):Handbook of Hidden Markov Models in Bioinformatics, Chap-man and Hall / CRC, Boca Raton, FL, 2008. doi: 10.1201/9781420011807.
• [85] Grenander U.:Syntax-controlled probabilities, Tech. rep., Brown University,Providence, R.I., 1967.
• [86] Harmanci A.O., Sharma G., Mathews D.H.: Efficient pairwise RNA structureprediction using probabilistic alignment constraints inDynalign,BMC Bioin-formatics, vol. 8, 130, 2007.
• [87] Haussler D., Krogh A., Mian I.S., Sj ̈oander K.: Protein modeling using hiddenMarkov models: analysis of globins. In:Proceedings of 26th Annual HawaiiInternational Conference on Systems Sciences, pp. 792–802, 1993.
• [88] Head T.: Formal language theory and DNA: an analysis of the generative capac-ity of specific recombinant behaviors,Bulletin of Mathematical Biology, vol. 49,pp. 737–759, 1987. doi: 10.1016/s0092-8240(87)90018-8.
• [89] Holmes I., Rubin G.M.: Pairwise RNA structure comparison with stochasticcontext-free grammars. In:Proceedings of 2002 Pacific Symposium on Biocom-puting, pp. 163–174, Hawaii, 2002.
• [90] Horan K., Shelton C., Girke T.: Predicting conserved protein motifs with Sub-HMMs,BMC Bioinformatics, vol. 11, 205, 2010. doi: 10.1186/1471-2105-11-205.
• [91] Hsu B.Y., Wong T.K.F., Hon W.K., Liu X., Lam T.W., Yiu S.M.: A LocalStructural Prediction Algorithm for RNA Triple Helix Structure. In: A. Ngom,E. Formenti, J.K. Hao, X.M. Zhao, T. van Laarhoven (eds.),Pattern Recognitionin Bioinformatics. PRIB 2013.Lecture Notes in Computer Science, vol. 7968,pp. 102–113, 2013. doi: 10.1007/978-3-642-39159-010.
• [92] Huang T., Fu K.S.: Stochastic syntactic analysis for programmed grammars andsyntactic pattern recognition,Computer Graphics and Image Processing, vol. 1,pp. 257–283, 1972. doi: 10.1016/s0146-664x(72)80018-2.
• [93] Janssen S., Giegerich R.: Faster computation of exact RNA shape probabilities,Bioinformatics, vol. 26, pp. 632–639, 2010. doi: 10.1093/bioinformatics/btq014.
• [94] Janssens D., Rozenberg G.: On the structure of node-label-controlled graphlanguages,Information Sciences, vol. 20, pp. 191–216, 1980. doi: 10.1016/0020-0255(80)90038-9.
• [95] Janssens D., Rozenberg G.: Restrictions, extensions, and variations of NLCgrammars,Information Sciences, vol. 20, pp. 217–244, 1980. doi: 10.1016/0020-0255(80)90039-0.
• [96] Janssens D., Rozenberg G.: Graph grammars with neighbourhood-controlledembedding,Theoretical Computer Science, vol. 21, pp. 55–74, 1982.doi: 10.1016/0304-3975(82)90088-3.
• [97] Janssens D., Rozenberg G., Verraedt R.: On sequential and parallel node-rewriting graph grammars,Computer Graphics and Image Processing, vol. 18,pp. 279–304, 1982. doi: 10.1016/0146-664x(82)90036-3.
• [98] Johnson L.S., Eddy S.R., Portugaly L.: Hidden Markov model speed heuristicand iterative HMM search procedure,BMC Bioinformatics, vol. 11, 431, 2010.doi: 10.1186/1471-2105-11-431.
• [99] Jonyer I., Holder L.B., Cook D.J.: MDL-based context-free graph grammar in-duction and applications,International Journal on Artificial Intelligence Tools,vol. 13, pp. 65–79, 2004. doi: 10.1142/s0218213004001429.
• [100] Joshi A.K.: How much context-sensitivity is necessary for characterizing struc-tural descriptions – Tree Adjoining Grammars. In: D. Dowty,et al.(eds.),Natural Language Processing – Theoretical, Computational and PsychologicalPerspective, Cambridge University Press, New York, NY, 1985.
• [101] Joshi A.K., Levy L.S., Takahashi M.: Tree adjunct grammars,Journal of Com-puter and System Sciences, vol. 10, pp. 136–163, 1975. doi: 10.1016/s0022-0000(75)80019-5.
• [102] Joshi A.K., Schabes Y.: Tree adjoining grammars. In: G. Rozenberg, A. Salomaa(eds.),Handbook of Formal Languages – III, pp. 69–123, Springer, New York,NY, 1997. doi: 10.1007/978-3-642-59126-62.
• [103] K ̈all L., Krogh A., Sonnhammer E.: An HMM posterior decoder for sequencefeature prediction that includes homology information,Bioinformatics, vol. 21,pp. i251–i257, 2005. doi: 10.1093/bioinformatics/bti1014.
• [104] Karplus K., Barrett C., Hughey R.: Hidden Markov models for detecting remoteprotein homologies,Bioinformatics, vol. 14, pp. 846–856, 1998. doi: 10.1093/bioinformatics/14.10.846.
• [105] Kato Y., Akutsu T., Seki H.: A grammatical approach to RNA-RNA interac-tion prediction,Pattern Recognition, vol. 42, pp. 531–538, 2009. doi: 10.1016/j.patcog.2008.08.004.
• [106] Kato Y., Seki H., Kasami T.: Subclasses of tree adjoining grammars for RNAsecondary structure. In:Proceedings of 7th International Workshop on Tree Ad-joining Grammar and Related Formalisms, pp. 48–55, Vancouver, Canada, 2004.
• [107] Kato Y., Seki H., Kasami T.: Stochastic multiple context-free grammar forRNA pseudoknot modeling. In:Proceedings of 8th International Workshop onTree Adjoining Grammar and Related Formalisms, pp. 57–64, Sydney, Australia,2006. doi: 10.3115/1654690.1654698.
• [108] Kennedy P.J., Osborn T.R.: A model of gene expression and regulation in anartificial cellular organism,Complex Systems, vol. 13, pp. 33–59, 2001.
• [109] Kirsch R.A.: Computer determination of the constituent structure of bio1ogicalimages,Computers and Biomedical Research, vol. 4, pp. 315–328, 1971.doi: 10.1016/0010-4809(71)90034-6.
• [110] Knudsen B., Hein J.: RNA secondary structure prediction using stochas-tic context-free grammars and evolutionary history,Bioinformatics, vol. 15,pp. 446–454, 1999. doi: 10.1093/bioinformatics/15.6.446.
• [111] Knudsen B., Hein J.: Pfold: RNA secondary structure prediction using stochas-tic context-free grammars,Nucleic Acids Research, vol. 31, pp. 3423–3428, 2003.
• [112] Knudsen B., Miyamoto M.M.: Sequence alignments and pair hidden Markovmodels using evolutionary history,Journal of Molecular Biology, vol. 333,pp. 453–460, 2003. doi: 10.1016/j.jmb.2003.08.015.
• [113] Knuth D.: Semantics of context-free languages,Mathematical Systems Theory,vol. 2, pp. 127–145, 1968. doi: 10.1007/bf01692511.
• [114] Koutroumbas K., Theodoridis S.:Pattern Recognition, Academic Press,Boston, 2008.
• [115] Krogh A., Brown M., Mian I.S., Sj ̈oander K., Haussler D.: Hidden Markovmodels in computational biology: Applications to protein modeling,Journal ofMolecular Biology, vol. 235, pp. 1501–1531, 1994.
• [116] Krogh A., Larsson B., Heijne von G., Sonnhammer E.: Predicting transmem-brane protein topology with a hidden Markov model: application to completegenomes,Journal of Molecular Biology, vol. 305, pp. 567–580, 2001.
• [117] Krogh A., Mian I.S., Haussler D.: A hidden Markov model that finds genes inE. coli DNA,Nucleic Acids Research, vol. 22, pp. 4768–4778, 1994.
• [118] Kulp D., Haussler D., Reese M.G., Eeckman F.H.: A Generalized HiddenMarkov Model for the Recognition of Human Genes in DNA. In:Proceedings ofthe 4th International Conference on Intelligent Systems for Molecular Biology,pp. 134–142, St. Louis, MO, USA, 1996.
• [119] Lasfar M., Bouden H.: A method of data mining using Hidden Markov Models(HMMs) for protein secondary structure prediction,Procedia Computer Science,vol. 127, pp. 42–51, 2018. doi: 10.1016/j.procs.2018.01.096.
• [120] Ledley R.S.: High-speed automatic analysis of biomedical pictures,Science,vol 146, pp. 216–223, 1964. doi: 10.1126/science.146.3641.216.
• [121] Ledley R.S., Rotolo L.S., Golab T.J., Jacobsen J.D., Ginsberg M.D., Wil-son J.B.: FIDAC: Film input to digital automatic computer and associ-ated syntax-directed pattern-recognition programming system. In: J.T. Tippet,D. Beckovitz, L. Clapp, C. Koester, A. Vanderburgh Jr. (eds.),Optical andElectro-optical Information Processing, pp. 591–613, MIT Press, Cambridge,MA, 1965.
• [122] Lee H.C., Fu K.S.: A stochastic syntax analysis procedure and its application topattern classification,IEEE Transactions on Computers, vol. 21, pp. 660–666,1972. doi: 10.1109/t-c.1972.223571.
• [123] Lefebvre F.: A grammar-based unification of several alignment and folding algo-rithms. In:Proceedings of 4th International Conference on Intelligent Systemsfor Molecular Biology, pp. 143–154, St. Louis, MO, USA, 1996.
• [124] Leung S.,Mellish C.,Robertson D.:Basic Gene Grammars andDNA-ChartParser for language processing ofEscherichia colipromoter DNAsequences,Bioinformatics, vol. 17, pp. 226–236, 2001.
• [125] Levenshtein V.I.: Binary codes capable of correcting deletions, insertions andreversals,Soviet Physics Doklady, vol. 10, pp. 707–710, 1966.
• [126] Li J., Lee J., Liao L.: A new algorithm to train hidden Markov models forbiological sequences with partial labels,BMC Bioinformatics, vol. 22, 162, 2021.doi: 10.1186/s12859-021-04080-0.
• [127] Li M., Cheng M., Ye Y., Hon W., Ting H., Lam T., Tang C.,et al.:Predicting RNA secondary structures: One-grammar-fits-all solution,LectureNotes in Computer Science, vol. 9096, pp. 211–222, 2015. doi: 10.1007/978-3-319-19048-818.
• [128] Liang K.C., Wang X., Anastassiou D.: Bayesian Basecalling for DNA SequenceAnalysis Using Hidden Markov Models,IEEE/ACM Transactions on Compu-tational Biology and Bioinformatics, vol. 4(3), pp. 430–440, 2007. doi: 10.1109/tcbb.2007.1027.
• [129] Liu L., Mori T., Zhao Y., Hayashida M., Akutsu T.: Euler string-basedcompression of tree-structured data and its application to analysis ofRNAs,Current Bioinformatics, vol. 13, pp. 25–33, 2018.doi: 10.2174 /1574893611666160608102231.
• [130] Lobo D., Vico F.J., Dassow J.: Graph grammars with string-regulated rewriting,Theoretical Computer Science, vol. 412, pp. 6101–6111, 2011. doi: 10.1016/j.tcs.2011.07.004.
• [131] Lottaz C., Iseli C., Jongeneel C.V., Bucher P.: Modeling sequencing er-rors by combining hidden Markov models,Bioinformatics, vol. 19 (Suppl. 2),pp. i103–i112, 2003. doi: 10.1093/bioinformatics/btg1067.
• [132] Lu S.Y., Fu K.S.: Structure-preserved error-correcting tree automata for syn-tactic pattern recognition. In:1976 IEEE Conference on Decision and Controlincluding the 15th Symposium on Adaptive Processes, pp. 413–419, Clearwater,FL, USA, 1976. doi: 10.1109/cdc.1976.267768.
• [133] Lyngsø R.B., Pedersen C.N.: RNA pseudoknot prediction in energy-based mod-els,Journal of Computational Biology, vol. 7, pp. 409–427, 2000. doi: 10.1089/106652700750050862.
• [134] Majoros W.H., Pertea M., Delcher A.L., Salzberg S.L.: Efficient decoding algo-rithms for generalized hidden Markov model gene finders,BMC Bioinformatics,vol. 6, 16, 2005. doi: 10.1186/1471-2105-6-16.
• [135] Mamitsuka H., Abe N.: Predicting location and structure of beta-sheet regionsusing stochastic tree grammars. In:Proceedings of 2nd International Confer-ence on Intelligent Systems for Molecular Biology, pp. 276–284, Stanford, CA,USA, 1994.
• [136] Mamuye A., Merelli E., Tesei L.: A graph grammar for modelling RNA folding.In:Proceedings of 2nd Graphs as Models Workshop, pp. 31–41, Eindhoven, TheNetherlands, 2016. doi: 10.4204/eptcs.231.3.
• [137] Marchand B., Will S., Berkemer S.J., Ponty Y., Bulteau L.: Automateddesign of dynamic programming schemes for RNA folding with pseudoknots.In:Proceedings of 22nd International Workshop on Algorithms in Bioinformat-ics, pp. 7:1–7:24, Potsdam, Germany, 2022. doi: 10.1186/s13015-023-00229-z.
• [138] Markov A.A.: Essai d’une recherche statistique sur le texte du romanEu-gene Oneginillustrant la liaison des epreuve en chain,Bulletin de l’Acad ́emieImp ́eriale des Sciences de St-P ́etersbourg, vol. 7, pp. 153–162, 1913.
• [139] Matsui H., Sato K., Sakakibara Y.: Pair stochastic tree adjoining grammarsfor aligning and predicting pseudoknot RNA structures,Bioinformatics, vol. 21,pp. 2611–2617, 2005. doi: 10.1093/bioinformatics/bti385.
• [140] Menichelli C., Gascuel O., Br ́eh ́elin L.: Improving pairwise comparison of pro-tein sequences with domain co-occurrence,PLoS Computational Biology, vol. 14,e1005889, 2018. doi: 10.1371/journal.pcbi.1005889.
• [141] Muggleton S., Bryant C., Srinivasan A., Whittaker A., Topp S., Rawlings C.:Are grammatical representations useful for learning from biological sequencedata? A case study,Journal of Computational Biology, vol. 8, pp. 493–522, 2001.
• [142] Munch K., Krogh A.: Automatic generation of gene finders for eukaryoticspecies,BMC Bioinformatics, vol. 7, 263, 2006. doi: 10.1186/1471-2105-7-263.
• [143] Nebel M.E., Weinberg F.: Algebraic and combinatorial properties of commonRNA pseudoknot classes with applications,Journal of Computational Biology,vol. 19, pp. 1134–1150, 2012. doi: 10.1089/cmb.2011.0094.
• [144] Pachter L., Alexandersson M., Cawley S.: Applications of generalized pair hid-den Markov models to alignment and gene finding problems,Journal of Com-putational Biology, vol. 9, pp. 389–399, 2002. doi: 10.1089/10665270252935520.
• [145] Pavlidis T.: Structural descriptions and graph grammars. In: S.K. Chang,K.S. Fu (eds.),Pictorial Information Systems, pp. 86–103, Springer, Berlin –Heidelberg – New York, 1980. doi: 10.1007/3-540-09757-04.
• [146] Pedersen J.C., Hein J.:Gene finding with a hidden Markov model ofgenome structure and evolution,Bioinformatics, vol. 19, pp. 219–227, 2003.doi: 10.1093/bioinformatics/19.2.219.
• [147] Peris P., L ́opez D., Campos M.: IgTM: An algorithm to predict transmem-brane domains and topology in proteins,BMC Bioinformatics, vol. 9, 367, 2008.doi: 10.1186/1471-2105-9-367.
• [148] Pl ̈otz T., Fink G.A.: Pattern recognition methods for advanced stochastic pro-tein sequence analysis using HMMs,Pattern Recognition, vol. 39, pp. 2267–2280,2006. doi: 10.1016/j.patcog.2005.10.007.
• [149] Ponty Y.:Ensemble Algorithms and Analytic Combinatorics in RNA Bioinfor-matics and Beyond, Universit ́e Paris-Saclay, 2020.
• [150] Porter T., Hajibabaei M.: Profile hidden Markov model sequence analysis canhelp remove putative pseudogenes from DNA barcoding and metabarcodingdatasets,BMC Bioinformatics, vol. 22, 256, 2021. doi: 10.1186/s12859- 021-04180-x.
• [151] Przytycka T., Srinivasan R., Rose G.D.: Recursive domains in proteins,ProteinScience, vol. 11, pp. 409–417, 2002. doi: 10.1110/ps.24701.
• [152] Quadrini M., Tesei L., Merelli E.: An algebraic language for RNA pseudoknotscomparison,BMC Bioinformatics, vol. 20, 161, 2019. doi: 10.1186/s12859-019-2689-5.
• [153] Rabin M.O.:Probabilistic automata,Information and Control, vol. 6,pp. 230–245, 1963. doi: 10.1016/s0019-9958(63)90290-0.
• [154] Reese M.G., Kulp D., Tammana H., Haussler D.:Genie– gene finding inDrosophila melanogaster,Genome Research, vol. 10, pp. 529–538, 2000.
• [155] Riechert M., zu Siederdissen H ̈oner C.H., Stadler P.F.: Algebraic dynamic pro-gramming for multiple context-free grammars,Theoretical Computer Science,vol. 639, pp. 91–109, 2016. doi: 10.1016/j.tcs.2016.05.032.
• [156] Ripley B.D.:Pattern Recognition and Neural Networks, Cambridge UniversityPress, Cambridge, 2008.
• [157] Rivas E., Eddy S.R.: The language of RNA: a formal grammar that includespseudoknots,Bioinformatics, vol. 16(4), pp. 334–340, 2000. doi: 10.1093/bioinformatics/16.4.334.
• [158] Rivas E., Eddy S.R.: Noncoding RNA gene detection using comparativesequence analysis,BMC Bioinformatics, vol. 2, 8, 2001. doi: 10.1186/1471-2105-2-8.
• [159] Rosenblueth D.A., Thieffry D., Huerta A.M., Salgado H., Collado-Vides J.:Syntactic recognition of regulatory regions inEscherichia coli,Computer Appli-cations in the Biosciences, vol. 12, pp. 415–422, 1996.
• [160] Rosenkrantz D.J.: Programmed grammars and classes of formal languages,Journal of the Association for Computing Machinery, vol. 16, pp. 107–131, 1969.doi: 10.1145/321495.321504.
• [161] Sakakibara Y.: Grammatical inference in bioinformatics,IEEE Transactionson Pattern Analysis and Machine Intelligence, vol. 27, pp. 1051–1062, 2005.doi: 10.1109/tpami.2005.140
• [162] Sakakibara Y., Brown M., Hughey R., Mian I.S., Sj ̈olander K., Underwood R.C.,Haussler D.: Stochastic context-free grammars for tRNA modeling,NuclearAcids Research, vol. 22(23), pp. 5112–5120, 1994. doi: 10.1093/nar/22.23.5112.
• [163] Salomaa A.: Probabilistic and weighted grammars,Information and Control,vol. 15, pp. 529–544, 1969. doi: 10.1016/s0019-9958(69)90554-3.
• [164] Sanchez-Graillet O., Poesio M.: Negation of protein-protein interactions:analysis and extraction,Bioinformatics, vol. 23, pp. i424–i432, 2007.doi: 10.1093/bioinformatics/btm184.
• [165] Sato K., Hamada M.: Recent trends in RNA informatics: a review of machinelearning and deep learning for RNA secondary structure prediction and RNAdrug discovery,Briefings in Bioinformatics, vol. 24, 2023. doi: 10.1093/bib/bbad186.
• [166] Sauthoff G., Giegerich R.: Yield grammar analysis and product optimizationin a domain-specific language for dynamic programming,Science of ComputerProgramming, vol. 87, pp. 2–22, 2014. doi: 10.1016/j.scico.2013.09.011.
• [167] Schalkoff R.:Pattern Recognition: Statistical, Structural and Neural Ap-proaches, Wiley, New York, 2005.
• [168] Searls D.B.:The linguistics of DNA,American Scientist, vol. 80(6),pp. 579–591, 1992.
• [169] Searls D.B.: The computational linguistics of biological sequences. In: L. Hunter(ed.),Artificial Intelligence and Molecular Biology, pp. 47–120, AAAI/MITPress, Menlo Park, CA, 1993.
• [170] Searls D.B.: String Variable Grammar: a logic grammar formalism for DNAsequences,The Journal of Logic Programming, vol. 24, pp. 73–102, 1995.
• [171] Searls D.B.: Linguistic approaches to biological sequences,Bioinformatics,vol. 13, pp. 333–344, 1997. doi: 10.1093/bioinformatics/13.4.333.
• [172] Searls D.B.: Reading the book of life,Bioinformatics, vol. 17, pp. 579–580, 2001.doi: 10.1093/bioinformatics/17.7.579.
• [173] Searls D.B.: The language of genes,Nature, vol. 420, pp. 211–217, 2002.doi: 10.1038/nature01255.
• [174] Seesi S.A.,Rajasekaran S.,Ammar R.:Pseudoknot Identificationthrough Learning TAGRNA. In: M. Chetty, A. Ngom, S. Ahmad (eds.),PatternRecognition in Bioinformatics. PRIB 2008.Lecture Notes in Computer Science,vol. 5265, pp. 132–143, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-88436-112.
• [175] Seki H., Matsumura T., Fujii M., Kasami T.: On multiple context-free gram-mars,Theoretical Computer Science, vol. 88, pp. 191–229, 1991. doi: 10.1016/0304-3975(91)90374-b.
• [176] Seoud R.A.A., Youssef A.B.M., Kadah Y.M.: Extraction of protein interactioninformation from unstructured text using a link grammar parser. In:Proceed-ings of 2007 International Conference on Computer Engineering and Systems,pp. 70–75, Cairo, Egypt, 2007. doi: 10.1109/icces.2007.4447028.
• [177] Shen X., Vikalo H.: ParticleCall: A particle filter for base calling in next-generation sequencing systems,BMC Bioinformatics, vol. 13, 160, 2012.doi: 10.1186/1471-2105-13-160.
• [178] Siederdissen zu C.H., Hofacker I.L., Stadler P.F.: Product grammars for align-ment and folding,IEEE/ACM Transactions on Computational Biology andBioinformatics, vol. 12, pp. 507–519, 2015. doi: 10.1109/tcbb.2014.2326155.
• [179] Silva da W.M.C., Andersen J.L., Holanda M.T., Walter M.E.M.T.,Brigido M.M., Stadler P.F., Flamm C.: Exploring plant sesquiterpene di-versity by generating chemical networks,Processes, vol. 7, p. 240, 2019.doi: 10.3390/pr7040240.
• [180] Singh P., Bandyopadhyay P., Bhattacharya S., Krishnamachari A., Sengupta S.:Riboswitch detection using profile hidden Markov models,BMC Bioinformatics,vol. 10, 325, 2009. doi: 10.1186/1471-2105-10-325.
• [181] Slisenko A.O.: Context-free grammars as a tool for describing polynomial-timesubclasses of hard problems,Information Processing Letters, vol. 14, pp. 52–56,1982. doi: 10.1016/0020-0190(82)90086-2.
• [182] Smoly I., Carmel A., Shemer-Avni Y., Yeger-Lotem E., Ziv-Ukelson M.: Algo-rithms for regular tree grammar network search and their application to min-ing human-viral infection patterns,Journal of Computational Biology, vol. 23,pp. 165–179, 2016. doi: 10.1089/cmb.2015.0168.
• [183] S ̈oding J.: Protein homology detection by HMM-HMM comparison,Bioinfor-matics, vol. 21, pp. 951–960, 2005.
• [184] Srivastava P.K., Desai D.K., Nandi S., Lynn A.M.: HMM-ModE-improved clas-sification using profile hidden Markov models by optimising the discriminationthreshold and modifying emission probabilities with negative training sequences,BMC Bioinformatics, vol. 8, 104, 2007. doi: 10.1186/1471-2105-8-104.
• [185] St-Onge K., Thibault P., Hamel S., Major F.: Modeling RNA tertiary structuremotifs by graph-grammars,Nucleic Adids Research, vol. 35, pp. 1726–1736,2007. doi: 10.1093/nar/gkm069.
• [186] Sun Y., Buhler J.: Designing patterns for profile HMM search,Bioinformatics,vol. 23, pp. e36–e43, 2006. doi: 10.1093/bioinformatics/btl323.
• [187] Sun Y., Buhler J.:Designing patterns and profiles for faster HMMsearch,IEEE/ACM Trans Computational Biology and Bioinformatics, vol. 6,pp. 232–243, 2009. doi: 10.1109/tcbb.2008.14.
• [188] Tamposis I.A., Tsirigos K.D., Theodoropoulou M.C., Kontou P.I., Bagos P.G.:Semi-supervised learning of hidden Markov models for biological sequenceanalysis,Bioinformatics, vol. 35, pp. 2208–2215, 2019.doi: 10.1093 /bioinformatics/bty910.
• [189] Tanaka E., Ikeda M., Ezure K.: Direct parsing,Pattern Recognition, vol. 19,pp. 315–323, 1986. doi: 10.1016/0031-3203(86)90057-9.
• [190] Temkin J.M., Gilder M.R.: Extraction of protein interaction informationfrom unstructured text using a context-free grammar,Bioinformatics, vol. 19,pp. 2046–2053, 2003. doi: 10.1093/bioinformatics/btg279.
• [191] Terrapon N., Gascuel O., Mar ́echal E., Br ́eh ́elin L.: Fitting hidden Markov mod-els of protein domains to a target species: application toPlasmodium falciparum,BMC Bioinformatics, vol. 13, p. 67, 2012. doi: 10.1186/1471-2105-13-67.
• [192] Thomason M.G., Gonzales R.C.: Syntactic recognition of imperfectly spec-ified patterns,IEEE Transactions on Computers, vol. 24, pp. 93–95, 1975.doi: 10.1109/t-c.1975.224086.
• [193] Tsafnat G., Schaeffer J., Clayphan A., Iredell J.R., Partridge S.R., Coiera E.:Computational inference of grammars for larger-than-gene structures from anno-tated gene sequences,Bioinformatics, vol. 27, pp. 791–796, 2011. doi: 10.1093/bioinformatics/btr036.
• [194] Turakainen P.: On stochastic languages,Information and Control, vol. 12,pp. 304–313, 1968. doi: 10.1016/s0019-9958(68)90360-4.
• [195] Tur ́an G.: On the complexity of graph grammars,Acta Cybernetica, vol. 6(3),pp. 271–280, 1983.
• [196] Uemura Y., Hasegawa A., Kobayashi S., Yokomori T.: Tree adjoining gram-mars for RNA structure prediction,Theoretical Computer Science, vol. 210,pp. 277–303, 1999. doi: 10.1016/s0304-3975(98)00090-5.
• [197] Vijayakumar J., Mathew L., Nagar A.K.: A new class of graph grammarsand modelling of certain biological structures,Symmetry, vol. 15, p. 349, 2023.doi: 10.3390/sym15020349.
• [198] Wang J., Keightley P.D., Johnson T.: MCALIGN2: faster, accurate global pair-wise alignment of non-coding DNA sequences based on explicit models of indelevolution,BMC Bioinformatics, vol. 7, 292, 2006. doi: 10.1186/1471-2105-7-292.
• [199] Weinberg Z., Ruzzo W.L.: Sequence-based heuristics for faster annotation ofnon-coding RNA families,Bioinformatics, vol. 22, pp. 35–39, 2006.
• [200] Wieczorek W., Unold O.: Use of a novel grammatical inference approach inclassification of amyloidogenic hexapeptides,Computational and MathematicalMethods in Medicine, vol. 2016, 1782732, 2016. doi: 10.1155/2016/1782732.
• [201] Wistrand M., Sonnhammer E.L.: Improving profile HMM discriminationby adapting transition probabilities,Journal of Molecular Biology, vol. 338,pp. 847–854, 2004. doi: 10.1016/j.jmb.2004.03.023.
• [202] Won K.J., Hamelryck T., Pr ̈ugel-Bennett A., Krogh A.: An evolutionary methodfor learning HMM structure: prediction of protein secondary structure,BMCBioinformatics, vol. 8, 357, 2007. doi: 10.1186/1471-2105-8-357.
• [203] Yandell M.D., Majoros W.H.: Genomics and natural language processing,Na-ture Reviews Genetics, vol. 3, pp. 601–610, 2002. doi: 10.1038/nrg861.
• [204] Yokomori T., Kobayashi S.: Learning local languages and their application toDNA sequence analysis,IEEE Transactions on Pattern Analysis and MachineIntelligence, vol. 20, pp. 1067–1079, 1998. doi: 10.1109/34.722617.
• [205] Yoon B.J.: Hidden Markov models and their applications in biological se-quence analysis,Current Genomics, vol. 10, pp. 402–415, 2009. doi: 10.2174/138920209789177575.
• [206] Yoon B.J., Vaidyanathan P.P.: Structural alignment of RNAs using profile-csHMMs and its application to RNA homology search: Overview and newresults,IEEE Transactions on Automatic Control, vol. 53, pp. 10–25, 2008.doi: 10.1109/TAC.2007.911322.
• [207] Zadeh L.A.: Note on fuzzy languages,Information Sciences, vol. 1, pp. 421–434,1969. doi: 10.1016/0020-0255(69)90025-5.
• [208] Zehnder T., Benner P., Vingron M.: Predicting enhancers in mammaliangenomes using supervised hidden Markov models,BMC Bioinformatics, vol. 20,157, 2019. doi: 10.1186/s12859-019-2708-6.
• [209] Zhang S., Borovok I., Aharonowitz Y., Sharan R., Bafna V.: A sequence-basedfiltering method for ncRNA identification and its application to searching forriboswitch elements,Bioinformatics, vol. 22, pp. e557–e565, 2006. doi: 10.1093/bioinformatics/btl232.
• [210] Zhao Y., Hayashida M., Akutsu T.: Integer programming-based method forgrammar-based tree compression and its application to pattern extraction ofglycan tree structures,BMC Bioinformatics, vol. 11, S4, 2010. doi: 10.1186/1471-2105-11-s11-s4.
• [211] Zhao Y., Hayashida M., Cao Y., Hwang J., Akutsu T.: Grammar-based com-pression approach to extraction of common rules among multiple trees of glycansand RNAs,BMC Bioinformatics, vol. 16, 128, 2015. doi: 10.1186/s12859-015-0558-4.
• [212] Zou L., Wang Z., Wang Y., Hu F.: Combined prediction of transmembranetopology and signal peptide ofβ-barrel proteins: Using a hidden Markovmodel and genetic algorithms,Computers in Biology and Medicine, vol. 40,pp. 621–628, 2010. doi: 10.1016/j.compbiomed.2010.04.006.