{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T01:40:59Z","timestamp":1649209259813},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2005,4]]},"abstract":"<jats:p> Several methods have been developed for identifying more or less complex RNA structures in a genome. All these methods are based on the search for conserved primary and secondary sub-structures. In this paper, we present a simple formal representation of a helix, which is a combination of sequence and folding constraints, as a constrained regular expression. This representation allows us to develop a well-founded algorithm that searches for all approximate matches of a helix in a genome. The algorithm is based on an alignment graph constructed from several copies of a pushdown automaton, arranged one on top of another. This is a first attempt to take advantage of the possibilities of pushdown automata in the context of approximate matching. The worst time complexity is O(krpn), where k is the error threshold, n the size of the genome, p the size of the secondary expression, and r its number of union symbols. We then extend the algorithm to search for pseudo-knots and secondary structures containing an arbitrary number of helices. <\/jats:p>","DOI":"10.1142\/s0219720005001065","type":"journal-article","created":{"date-parts":[[2005,4,15]],"date-time":"2005-04-15T07:52:15Z","timestamp":1113551535000},"page":"317-342","source":"Crossref","is-referenced-by-count":2,"title":["APPROXIMATE MATCHING OF STRUCTURED MOTIFS IN DNA SEQUENCES"],"prefix":"10.1142","volume":"03","author":[{"given":"NADIA","family":"EL-MABROUK","sequence":"first","affiliation":[{"name":"D\u00e9partement d'informatique et de recherche op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, CP 6128 Succursale Centre-ville, Montr\u00e9al, Qu\u00e9bec H3C 3J7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATHIEU","family":"RAFFINOT","sequence":"additional","affiliation":[{"name":"CNRS \u2014 Equipe G\u00e9nome et Informatique, Evry, and ENS, 46 rue d'Ulm, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JEAN-EUDES","family":"DUCHESNE","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'informatique et de recherche op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATHIEU","family":"LAJOIE","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'informatique et de recherche op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NICOLAS","family":"LUC","sequence":"additional","affiliation":[{"name":"GEREQ Inc.1450 City Councillors Bureau 790, Montr\u00e9al, Qu\u00e9bec H3A 2E6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/24.8.1395"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/13.9.3021"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/22.11.2079"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1996.0622"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/565196.565216"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(91)90108-I"},{"key":"rf8","volume":"297","author":"Gaspin C.","journal-title":"J. Mol. Biol."},{"key":"rf9","first-page":"325","volume":"6","author":"Gautheret D.","journal-title":"Comput. Appl. Biosci."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/29.1.196"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1038\/387493a0"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1994.1074"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/25.5.0955"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1126\/science.283.5405.1168"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/29.22.4724"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00007-Y"},{"key":"rf17","first-page":"33","volume":"3","author":"Myers E. W.","journal-title":"J. Mol. Biol."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02458834"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1126\/science.288.5465.517"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/16.4.334"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63220-4_62"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/22.23.5112"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/27.1.158"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720005001065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:10:47Z","timestamp":1565183447000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720005001065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4]]},"references-count":24,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2005,4]]}},"alternative-id":["10.1142\/S0219720005001065"],"URL":"https:\/\/doi.org\/10.1142\/s0219720005001065","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,4]]}}}