{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T19:10:05Z","timestamp":1758395405433},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"17","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Searching RNA gene occurrences in genomic sequences is a task whose importance has been renewed by the recent discovery of numerous functional RNA, often interacting with other ligands. Even if several programs exist for RNA motif search, none exists that can represent and solve the problem of searching for occurrences of RNA motifs in interaction with other molecules.<\/jats:p>\n               <jats:p>Results: We present a constraint network formulation of this problem. RNA are represented as structured motifs that can occur on more than one sequence and which are related together by possible hybridization. The implemented tool MilPat is used to search for several sRNA families in genomic sequences. Results show that MilPat allows to efficiently search for interacting motifs in large genomic sequences and offers a simple and extensible framework to solve such problems. New and known sRNA are identified as H\/ACA candidates in Methanocaldococcus jannaschii.<\/jats:p>\n               <jats:p>Availability: \u00a0<\/jats:p>\n               <jats:p>Contact: \u00a0milpat@toulouse.inra.fr<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl354","type":"journal-article","created":{"date-parts":[[2006,7,6]],"date-time":"2006-07-06T01:54:39Z","timestamp":1152150879000},"page":"2074-2080","source":"Crossref","is-referenced-by-count":18,"title":["Searching RNA motifs and their intermolecular contacts with constraint networks"],"prefix":"10.1093","volume":"22","author":[{"given":"P.","family":"Th\u00e9bault","sequence":"first","affiliation":[{"name":"Unit\u00e9 de Biom\u00e9trie & Intelligence Artificielle INRA, Chemin de Borde Rouge 1 \u00a0 1 \u00a0 \u00a0 Auzeville, BP 52627, 31326 Castanet-Tolosan, France"},{"name":"Plateforme Bioinformatique, INRA 2 \u00a0 2 \u00a0 \u00a0 Chemin de Borde Rouge, Auzeville, BP 52627, 31326 Castanet-Tolosan, France"}]},{"given":"S.","family":"de Givry","sequence":"additional","affiliation":[{"name":"Unit\u00e9 de Biom\u00e9trie & Intelligence Artificielle INRA, Chemin de Borde Rouge 1 \u00a0 1 \u00a0 \u00a0 Auzeville, BP 52627, 31326 Castanet-Tolosan, France"}]},{"given":"T.","family":"Schiex","sequence":"additional","affiliation":[{"name":"Unit\u00e9 de Biom\u00e9trie & Intelligence Artificielle INRA, Chemin de Borde Rouge 1 \u00a0 1 \u00a0 \u00a0 Auzeville, BP 52627, 31326 Castanet-Tolosan, France"}]},{"given":"C.","family":"Gaspin","sequence":"additional","affiliation":[{"name":"Unit\u00e9 de Biom\u00e9trie & Intelligence Artificielle INRA, Chemin de Borde Rouge 1 \u00a0 1 \u00a0 \u00a0 Auzeville, BP 52627, 31326 Castanet-Tolosan, France"}]}],"member":"286","published-online":{"date-parts":[[2006,7,4]]},"reference":[{"key":"2023012409152537000_b1","article-title":"The at most \u03ba-deep factor tree","volume-title":"Technical Report # 2004-03","author":"Allali","year":"2004"},{"key":"2023012409152537000_b2","first-page":"10","article-title":"Constraint satisfaction techniques for modeling large complexes: application to the central domain of 16s ribosomal RNA","author":"Altman","year":"1994"},{"key":"2023012409152537000_b3","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","article-title":"A new approach to text searching","volume":"35","author":"Baeza-Yaltes","year":"1992","journal-title":"Communi. ACM'"},{"key":"2023012409152537000_b4","doi-asserted-by":"crossref","first-page":"1238","DOI":"10.1101\/gad.1309605","article-title":"RNA-guided RNA modification: functional organization of the archaeal H\/ACA RNP","volume":"19","author":"Baker","year":"2005","journal-title":"Genes Develop."},{"key":"2023012409152537000_b5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1023\/A:1020577603762","article-title":"PSICO: Solving protein structure with cconstraint programming and optimization","volume":"7","author":"Barahona","year":"2002","journal-title":"Constraints"},{"key":"2023012409152537000_b6","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1093\/nar\/24.8.1395","article-title":"Palingol: a declarative programming language to describe nucleic acids' secondary structures and to scan sequence database","volume":"24","author":"Billoud","year":"1996","journal-title":"Nucleic Acids Res."},{"key":"2023012409152537000_b7","first-page":"1315","article-title":"Refining the structure of a stochastic context-free grammar","author":"Bockhorst","year":"2001"},{"key":"2023012409152537000_b8","doi-asserted-by":"crossref","first-page":"3133","DOI":"10.1093\/nar\/gki630","article-title":"Reconstitution of archaeal H\/ACA small ribonucleoprotein complexes active in pseudourydilation","volume":"33","author":"Charpentier","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012409152537000_b9","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/S0168-9525(97)01347-4","article-title":"Searching for patterns in genomic data","volume":"13","author":"Dsouza","year":"1997","journal-title":"Trends Genet."},{"key":"2023012409152537000_b10","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","article-title":"RNA sequence analysis using covariance models","volume":"22","author":"Eddy","year":"1994","journal-title":"Nucleic Acids Res"},{"key":"2023012409152537000_b11","article-title":"Rnabob: a program to search for RNA secondary structure motifs in sequence databases","author":"Eddy","year":"1996","journal-title":"Manual"},{"key":"2023012409152537000_b12","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1023\/A:1011481521835","article-title":"A constraint based structure description language for biosequences","volume":"6","author":"Eidhammer","year":"2001","journal-title":"Constraints"},{"key":"2023012409152537000_b13","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1006\/jmbi.1995.0608","article-title":"An interactive framework for RNA secondary structure prediction with a dynamical treatment of constraints","volume":"254","author":"Gaspin","year":"1995","journal-title":"J. Mol. Biol."},{"key":"2023012409152537000_b14","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1006\/jmbi.2000.3593","article-title":"Archaeal homologs of eukaryotic methylation guide small nucleolar RNAs: lessons from the pyrococcus genomes","volume":"297","author":"Gaspin","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023012409152537000_b15","first-page":"325","article-title":"Pattern searching\/alignment with RNA primary and secondary structures: an effective descriptor for tRNA","volume":"6","author":"Gautheret","year":"1990","journal-title":"Comput. Appl. Biosci."},{"key":"2023012409152537000_b16","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","article-title":"A generic arc-consistency algorithm and its specializations","volume":"57","author":"Hentenryck","year":"1992","journal-title":"Artif. Intell."},{"key":"2023012409152537000_b17","doi-asserted-by":"crossref","first-page":"7542","DOI":"10.1073\/pnas.112063799","article-title":"Noncoding RNA genes identified in AT-rich hyperthermophiles","volume":"99","author":"Klein","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012409152537000_b18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","article-title":"Solving weighted CSP by maintaining arc consistency","volume":"159","author":"Larrosa","year":"2004","journal-title":"Artif. Intell."},{"key":"2023012409152537000_b19","doi-asserted-by":"crossref","first-page":"4724","DOI":"10.1093\/nar\/29.22.4724","article-title":"RNAMotif, an RNA secondary structure definition and search algorithm","volume":"29","author":"Macke","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023012409152537000_b20","doi-asserted-by":"crossref","first-page":"1255","DOI":"10.1126\/science.1716375","article-title":"The combination of symbolic and numerical computation for three-dimensional modeling of RNA","volume":"253","author":"Major","year":"1991","journal-title":"Science"},{"key":"2023012409152537000_b21","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1006\/jmbi.1998.1797","article-title":"Derivation of the three-dimensional architecture of bacterial ribonuclease p RNAs from comparative sequence analysis","volume":"279","author":"Massire","year":"1998","journal-title":"J. Mol. Biol."},{"key":"2023012409152537000_b22","first-page":"551","article-title":"Automatic display of RNA secondary structures","volume":"9","author":"Muller","year":"1993","journal-title":"Cabios"},{"key":"2023012409152537000_b23","first-page":"133","article-title":"Structured motifs search","author":"Policriti","year":"2004"},{"key":"2023012409152537000_b24","volume-title":"Handbook of Constraint Programming","author":"Rossi","year":"2006"},{"key":"2023012409152537000_b25","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1093\/nar\/gkg175","article-title":"Binding of L7Ae protein to the K-turn of archaeal snoRNAs: a shared RNA binding motif for C\/D and H\/ACA box snoRNAs in Archaea","volume":"31","author":"Rozhdestvensky","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012409152537000_b26","first-page":"289","article-title":"Recent methods for RNA modeling using stochastic context-free grammars","author":"Sakakibara","year":"1994"},{"key":"2023012409152537000_b27","doi-asserted-by":"crossref","first-page":"4281","DOI":"10.1093\/nar\/gkh768","article-title":"Genome-wide searching for pseudouridylation guide snornas: analysis of the Saccharomyces cerevisiae genome","volume":"32","author":"Schattner","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012409152537000_b28","doi-asserted-by":"crossref","first-page":"2076","DOI":"10.1093\/nar\/30.9.2076","article-title":"Searching for RNA genes using base-composition statistics","volume":"30","author":"Schattner","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023012409152537000_b29","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023012409152537000_b30","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1126\/science.1072249","article-title":"An expanding universe of noncoding RNAs","volume":"296","author":"Storz","year":"2002","journal-title":"Science"},{"key":"2023012409152537000_b31","first-page":"484","article-title":"Constructing suffix-trees on-line in linear time. Algorithms, Software, Architecture: Information Processing \u201992. Vol. 1","author":"Ukkonen","year":"1992"},{"key":"2023012409152537000_b32","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","article-title":"On the computational complexity of 2-interval pattern matching problems","volume":"312","author":"Vialette","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"2023012409152537000_b33","article-title":"Fast text searching with errors","volume-title":"Report TR-91-11","author":"Wu","year":"1991"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/17\/2074\/48841332\/bioinformatics_22_17_2074.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/17\/2074\/48841332\/bioinformatics_22_17_2074.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T09:55:53Z","timestamp":1674554153000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/17\/2074\/274197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,4]]},"references-count":33,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2006,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl354","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,9,1]]},"published":{"date-parts":[[2006,7,4]]}}}