{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:44Z","timestamp":1759638224626},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>It has become increasingly apparent that a comprehensive database of RNA motifs is essential in order to achieve new goals in genomic and proteomic research. Secondary RNA structures have frequently been represented by various modeling methods as graph-theoretic trees. Using graph theory as a modeling tool allows the vast resources of graphical invariants to be utilized to numerically identify secondary RNA motifs. The domination number of a graph is a graphical invariant that is sensitive to even a slight change in the structure of a tree. The invariants selected in this study are variations of the domination number of a graph. These graphical invariants are partitioned into two classes, and we define two parameters based on each of these classes. These parameters are calculated for all small order trees and a statistical analysis of the resulting data is conducted to determine if the values of these parameters can be utilized to identify which trees of orders seven and eight are RNA-like in structure.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>The statistical analysis shows that the domination based parameters correctly distinguish between the trees that represent native structures and those that are not likely candidates to represent RNA. Some of the trees previously identified as candidate structures are found to be \"very\" RNA like, while others are not, thereby refining the space of structures likely to be found as representing secondary RNA structure.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>Search algorithms are available that mine nucleotide sequence databases. However, the number of motifs identified can be quite large, making a further search for similar motif computationally difficult. Much of the work in the bioinformatics arena is toward the development of better algorithms to address the computational problem. This work, on the other hand, uses mathematical descriptors to more clearly characterize the RNA motifs and thereby reduce the corresponding search space. These preliminary findings demonstrate that graph-theoretic quantifiers utilized in fields such as computer network design hold significant promise as an added tool for genomics and proteomics.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-7-108","type":"journal-article","created":{"date-parts":[[2006,3,10]],"date-time":"2006-03-10T19:16:35Z","timestamp":1142018195000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":49,"title":["A quantitative analysis of secondary RNA structure using domination based parameters on trees"],"prefix":"10.1186","volume":"7","author":[{"given":"Teresa","family":"Haynes","sequence":"first","affiliation":[]},{"given":"Debra","family":"Knisley","sequence":"additional","affiliation":[]},{"given":"Edith","family":"Seier","sequence":"additional","affiliation":[]},{"given":"Yue","family":"Zou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,3,3]]},"reference":[{"key":"847_CR1","unstructured":"Science: Mapping RNA form and function Special Issue: 2 Sept 2005., 309(5740): [http:\/\/www.sciencemag.org\/sciext\/rna\/inscience]"},{"key":"847_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/0010-4809(89)90039-6","volume":"22","author":"S Le","year":"1989","unstructured":"Le S, Nussinov R, Maziel J: Tree graphs of RNA secondary structures and their comparisons. Comp Biomed Res 1989, 22: 461\u2013473. 10.1016\/0010-4809(89)90039-6","journal-title":"Comp Biomed Res"},{"key":"847_CR3","first-page":"179","volume":"22","author":"G Benedetti","year":"1996","unstructured":"Benedetti G, Morosetti S: A graph-topological approach to recognition of pattern and similarity in RNA secondary structures. Biol Chem 1996, 22: 179\u2013184.","journal-title":"Biol Chem"},{"key":"847_CR4","volume-title":"An Introduction to Computational Biology: Maps, Sequences and Genomes","author":"M Waterman","year":"2000","unstructured":"Waterman M: An Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman Hall\/CRC; 2000."},{"issue":"11","key":"847_CR5","doi-asserted-by":"publisher","first-page":"2926","DOI":"10.1093\/nar\/gkg365","volume":"31","author":"H Gan","year":"2003","unstructured":"Gan H, Pasquali S, Schlick T: Exploring the repertoire of RNA secondary motifs using graph theory; implications for RNA design. Nucleic Acids Research 2003, 31(11):2926\u20132943. 10.1093\/nar\/gkg365","journal-title":"Nucleic Acids Research"},{"key":"847_CR6","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1186\/1471-2105-5-88","volume":"5","author":"D Fera","year":"2004","unstructured":"Fera D, Kim N, Shiffeldrim N, Zorn J, Laserson U, Gan H, Schlick T: RAG: RNA-As-Graphs web resource. BMC Bioinformatics 2004, 5: 88. 10.1186\/1471-2105-5-88","journal-title":"BMC Bioinformatics"},{"key":"847_CR7","doi-asserted-by":"publisher","first-page":"1285","DOI":"10.1093\/bioinformatics\/bth084","volume":"20","author":"H Gan","year":"2004","unstructured":"Gan H, Fera D, Zorn J, Shiffeldrim N, Laserson U, Kim N, Schlick T: RAG: RNA-As-Graphs database \u2013 concepts, analysis, and features. Bioinformatics 2004, 20: 1285\u20131291. 10.1093\/bioinformatics\/bth084","journal-title":"Bioinformatics"},{"key":"847_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02559543","volume":"101","author":"F Harary","year":"1959","unstructured":"Harary F, Prins G: The number of homeomorphically irreducible trees and other species. Acta Math 1959, 101: 141\u2013162.","journal-title":"Acta Math"},{"key":"847_CR9","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1016\/j.jmb.2004.06.054","volume":"341","author":"N Kim","year":"2004","unstructured":"Kim N, Shiffeldrim N, Gan H, Schlick T: Candidates for novel RNA topologies. J Mol Biol 2004, 341: 1129\u20131144. 10.1016\/j.jmb.2004.06.054","journal-title":"J Mol Biol"},{"key":"847_CR10","volume-title":"Fundamentals of Domination in Graphs","author":"T Haynes","year":"1998","unstructured":"Haynes T, Hedetniemi S, Slater P: Fundamentals of Domination in Graphs. Marcel Dekker; 1998."},{"key":"847_CR11","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0020-0190(00)00142-3","volume":"76","author":"E Hartuv","year":"2000","unstructured":"Hartuv E, Shamir R: A clustering algorithms based on graph connectivity. Information Processing Letters 2000, 76: 175\u2013181. 10.1016\/S0020-0190(00)00142-3","journal-title":"Information Processing Letters"},{"key":"847_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1006\/jmbi.1998.1689","volume":"279","author":"R Samudrala","year":"1998","unstructured":"Samudrala R, Moult J: A graph-theoretic algorithm for comparative modeling of protein structure. J Mol Biol 1998, 279: 287\u2013302. 10.1006\/jmbi.1998.1689","journal-title":"J Mol Biol"},{"key":"847_CR13","first-page":"526","volume":"18","author":"Y Xu","year":"2002","unstructured":"Xu Y, Olman V, Xu D: Clustering gene expression data using a graph-theoretic approach: An application of minimum spanning trees. Bioinformatic 2002, 18: 526\u2013535.","journal-title":"Bioinformatic"},{"key":"847_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01200826","volume":"7","author":"S Basak","year":"1991","unstructured":"Basak S, Niemi G, Veith G: Predicting properties of molecules using graph invariants. J Math Chem 1991, 7: 243\u2013252. 10.1007\/BF01200826","journal-title":"J Math Chem"},{"key":"847_CR15","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jmbi.1999.3058","volume":"292","author":"K Kannan","year":"1999","unstructured":"Kannan K, Vishveshwara S: Identification of side-chain clusters in protein structures by a graph spectral method. J Mol Biol 1999, 292: 441\u2013464. 10.1006\/jmbi.1999.3058","journal-title":"J Mol Biol"},{"key":"847_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0301-4622(99)00134-9","volume":"84","author":"S Patra","year":"2000","unstructured":"Patra S, Vishveshwara S: Backbone cluster identification in proteins by a graph theoretical method. Biophysical Chemistry 2000, 84: 13\u201325. 10.1016\/S0301-4622(99)00134-9","journal-title":"Biophysical Chemistry"},{"key":"847_CR17","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0219633602000117","volume":"1","author":"S Vishveshwara","year":"2002","unstructured":"Vishveshwara S, Brinda K, Kannan N: Protein structures: insights from Graph Theory. J Theoretical and Computational Chemistry 2002, 1: 187\u2013211. 10.1142\/S0219633602000117","journal-title":"J Theoretical and Computational Chemistry"},{"key":"847_CR18","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0378-4274(95)03375-U","volume":"18","author":"S Basak","year":"1995","unstructured":"Basak S, Bertelsen S, Grunwald G: Use of graph theoretic parameters in risk assessment of chemicals. Toxicol Lett 1995, 18: 239\u2013248. 10.1016\/0378-4274(95)03375-U","journal-title":"Toxicol Lett"},{"key":"847_CR19","doi-asserted-by":"publisher","first-page":"4724","DOI":"10.1093\/nar\/29.22.4724","volume":"29","author":"T Macke","year":"2001","unstructured":"Macke T, Ecker D, Gutell R, Gautheret D, Case D, Sampath R: RNAMotif, an RNA secondary structure definition and search algorithm. Nucleic Acids Research 2001, 29: 4724\u20134735. 10.1093\/nar\/29.22.4724","journal-title":"Nucleic Acids Research"},{"key":"847_CR20","volume-title":"Chemical Graph Theory","author":"N Trinajstic","year":"1992","unstructured":"Trinajstic N Chemical Graph Theory CRC Press; 1992."},{"key":"847_CR21","volume-title":"Graph Theory and Its Applications","year":"1998","unstructured":"Yellen J, Gross J Graph Theory and Its Applications CRC Press; 1998."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-108.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T03:14:02Z","timestamp":1630466042000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-7-108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["847"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-7-108","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3,3]]},"assertion":[{"value":"20 October 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2006","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2006","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"108"}}