Alignment of RNA Secondary Structures with Arbitrary Pseudoknots using Structural Sequences

Alignment of RNA Secondary Structures with Arbitrary Pseudoknots using Structural Sequences | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Alignment of RNA Secondary Structures with Arbitrary Pseudoknots using Structural Sequences Luca Tesei, Francesca Levi, Michela Quadrini, Emanuela Merelli This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4831215/v2 This work is licensed under a CC BY 4.0 License Archived Versions: Posted Version 2 posted You are reading this latest preprint version Abstract Background Comparison of RNA secondary structures is fundamental for RNA classification, motifanalysis, and evolutionary studies. While efficient methods exist for pseudoknot-free structures, the comparison of RNAsecondary structures with arbitrary pseudoknots remains computationally challenging. Results We introduce a novel representation of RNA secondary structures with arbitrary pseudoknots based on integer sequences, called structural sequences. On this representation, we define the SERNA distance, an extension of the classical edit distance with structural correctness constraints, and prove that it is a metric. We present SERNAlign, an open-source tool that computes the SERNA distance using dynamic programming with quadratic time complexity. To evaluate the proposed distance, we conduct two complementary experiments within a clustering-based evaluation framework: classification of experimentally validated pseudoknot motifs, which directly targets the design goal of SERNA, and phylogenetic clustering of ribosomal RNAs as a robustness check against existing structural distances. Across both tasks, SERNA demonstrates competitive clustering performance with respect to state-of-the-art comparison methods, while providing improved discrimination in complex motif settings and significantly lower computational cost compared to structure-based approaches. Conclusions Structural sequences provide a precise and computationally efficient abstraction for RNA secondary structures with arbitrary pseudoknots. The associated SERNA distance captures global structural organization, enabling structure comparison and effective clustering of complex RNA secondary structures without relying on primary sequence information. By balancing representational power and computational efficiency, SERNA complements existing methods for RNA secondary structure comparison in pseudoknotted settings. RNA secondary structure comparison SERNA distance RNA context diagram Edit distance Dynamic programming Phylogeny reconstruction Full Text Additional Declarations Competing interest reported. The first author, Luca Tesei, is guest editor of the collection “Prediction and modelling of RNA structure and interactions” to which this paper is sent. Prof. Tesei declares a conflict of interest with the other guest editor Letizia Chiodo because they are working together in the project funding the paper. The third guest editor Anze Bozic could handle the paper without conflicts of interest. Alternatively, an external editor could handle the paper. Supplementary Files SupplementaryMaterialR1.pdf Cite Share Download PDF Archived Versions: Posted Version 2 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4831215","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[{"code":2,"date":"2026-03-23 16:11:52","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"bmc-bioinformatics","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"binf","sideBox":"Learn more about [BMC Bioinformatics](http://bmcbioinformatics.biomedcentral.com/)","snPcode":"","submissionUrl":"https://www.editorialmanager.com/binf","title":"BMC Bioinformatics","twitterHandle":"@BMC_Bioinformatics","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"em","reportingPortfolio":"BMC Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":610831958,"identity":"2dc64853-26d2-11f1-b2c4-06cc9d20a69f","order_by":0,"name":"Luca Tesei","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA2UlEQVRIiWNgGAWjYBACPjiLmfkAA4MBiMXYgFcLG5hMAGlhS4BpacSrB6GFgccAJojfGjaJ5IcfGH/Y2POz83yTLiiwk9dtYG5/gF9LmrEEQ0Ja4sxm3m3SMwySDbcdIOQwiRwGoJbDCQaHgVp4DA4wEqOF+QdDwn97+8M8z0Ba7InRwga05QDjBmYeNpCWRMJaeJ6ZWSSkJSfOOMxmbM1jkJy87TBj4wx8WvjZkx/f+GBjZ8/ff/jhbZ4/drbbjrc/+IBPCxgkoPCYCaofBaNgFIyCUUAIAAApR0CR24clmwAAAABJRU5ErkJggg==","orcid":"","institution":"University of Camerino","correspondingAuthor":true,"prefix":"","firstName":"Luca","middleName":"","lastName":"Tesei","suffix":""},{"id":610832028,"identity":"3838feae-26d2-11f1-b2c4-06cc9d20a69f","order_by":1,"name":"Francesca Levi","email":"","orcid":"","institution":"University of Pisa","correspondingAuthor":false,"prefix":"","firstName":"Francesca","middleName":"","lastName":"Levi","suffix":""},{"id":610832106,"identity":"46e547d9-26d2-11f1-b2c4-06cc9d20a69f","order_by":2,"name":"Michela Quadrini","email":"","orcid":"","institution":"University of Camerino","correspondingAuthor":false,"prefix":"","firstName":"Michela","middleName":"","lastName":"Quadrini","suffix":""},{"id":610832148,"identity":"55da8d19-26d2-11f1-b2c4-06cc9d20a69f","order_by":3,"name":"Emanuela Merelli","email":"","orcid":"","institution":"University of Camerino","correspondingAuthor":false,"prefix":"","firstName":"Emanuela","middleName":"","lastName":"Merelli","suffix":""}],"badges":[],"createdAt":"2024-07-30 21:33:25","currentVersionCode":2,"declarations":"","doi":"10.21203/rs.3.rs-4831215/v2","doiUrl":"https://doi.org/10.21203/rs.3.rs-4831215/v2","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":105224831,"identity":"c88c3295-10f1-42f8-9a4f-e04677d71b8f","added_by":"auto","created_at":"2026-03-23 16:16:39","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2021693,"visible":true,"origin":"","legend":"","description":"","filename":"paper.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4831215/v2_covered_542347bd-2811-4bae-b18b-ab64652d7923.pdf"},{"id":105224784,"identity":"8b36f6e6-f6b0-4b4d-9537-56a56a29b95c","added_by":"auto","created_at":"2026-03-23 16:16:11","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"supplement","size":3280478,"visible":true,"origin":"","legend":"","description":"","filename":"SupplementaryMaterialR1.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4831215/v2/489d7ce0c9dded2511f542cd.pdf"}],"financialInterests":"Competing interest reported. The first author, Luca Tesei, is guest editor of the collection “Prediction and modelling of RNA structure and interactions” to which this paper is sent. Prof. Tesei declares a conflict of interest with the other guest editor Letizia Chiodo because they are working together in the project funding the paper. The third guest editor Anze Bozic could handle the paper without conflicts of interest. Alternatively, an external editor could handle the paper.","formattedTitle":"Alignment of RNA Secondary Structures with Arbitrary Pseudoknots using Structural Sequences","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"bmc-bioinformatics","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"binf","sideBox":"Learn more about [BMC Bioinformatics](http://bmcbioinformatics.biomedcentral.com/)","snPcode":"","submissionUrl":"https://www.editorialmanager.com/binf","title":"BMC Bioinformatics","twitterHandle":"@BMC_Bioinformatics","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"em","reportingPortfolio":"BMC Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"RNA secondary structure comparison, SERNA distance, RNA context diagram, Edit distance, Dynamic programming, Phylogeny reconstruction","lastPublishedDoi":"10.21203/rs.3.rs-4831215/v2","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4831215/v2","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eBackground\u003c/p\u003e\n\u003cp\u003eComparison of RNA secondary structures is fundamental for RNA classification, motifanalysis, and evolutionary studies. While efficient methods exist for pseudoknot-free structures, the comparison of RNAsecondary structures with arbitrary pseudoknots remains computationally challenging.\u003c/p\u003e\n\u003cp\u003eResults\u003c/p\u003e\n\u003cp\u003eWe introduce a novel representation of RNA secondary structures with arbitrary pseudoknots based on integer sequences, called structural sequences. On this representation, we define the SERNA distance, an extension of the classical edit distance with structural correctness constraints, and prove that it is a metric. We present SERNAlign, an open-source tool that computes the SERNA distance using dynamic programming with quadratic time complexity. To evaluate the proposed distance, we conduct two complementary experiments within a clustering-based evaluation framework: classification of experimentally validated pseudoknot motifs, which directly targets the design goal of SERNA, and phylogenetic clustering of ribosomal RNAs as a robustness check against existing structural distances. Across both tasks, SERNA demonstrates competitive clustering performance with respect to state-of-the-art comparison methods, while providing improved discrimination in complex motif settings and significantly lower computational cost compared to structure-based approaches.\u003c/p\u003e\n\u003cp\u003eConclusions\u003c/p\u003e\n\u003cp\u003eStructural sequences provide a precise and computationally efficient abstraction for RNA secondary structures with arbitrary pseudoknots. The associated SERNA distance captures global structural organization, enabling structure comparison and effective clustering of complex RNA secondary structures without relying on primary sequence information. By balancing representational power and computational efficiency, SERNA complements existing methods for RNA secondary structure comparison in pseudoknotted settings.\u003c/p\u003e","manuscriptTitle":"Alignment of RNA Secondary Structures with Arbitrary Pseudoknots using Structural Sequences","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-08-30 03:12:37","doi":"10.21203/rs.3.rs-4831215/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-08-05T10:48:08+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-08-05T08:28:28+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-08-05T01:34:27+00:00","index":"","fulltext":""},{"type":"submitted","content":"BMC Bioinformatics","date":"2024-07-30T21:32:00+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"bmc-bioinformatics","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"binf","sideBox":"Learn more about [BMC Bioinformatics](http://bmcbioinformatics.biomedcentral.com/)","snPcode":"","submissionUrl":"https://www.editorialmanager.com/binf","title":"BMC Bioinformatics","twitterHandle":"@BMC_Bioinformatics","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"em","reportingPortfolio":"BMC Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true}},{"code":"","date":"2024-09-24 10:23:13","doi":"","editorialEvents":[{"type":"decision","content":"Revision requested","date":"2024-10-29T11:31:04+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-10-23T21:55:43+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-10-17T15:23:27+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"71065197978341630602752689837229355354","date":"2024-09-25T14:07:22+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"25665505962346504510493177741180806320","date":"2024-09-25T11:14:09+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-09-25T11:05:50+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-09-25T10:59:54+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-09-24T10:12:18+00:00","index":"","fulltext":""},{"type":"submitted","content":"BMC Bioinformatics","date":"2024-09-24T10:11:01+00:00","index":"","fulltext":""},{"type":"notPreprinted","content":""}],"status":"timeline","journal":{"display":true,"email":"[email protected]","identity":"bmc-bioinformatics","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"binf","sideBox":"Learn more about [BMC Bioinformatics](http://bmcbioinformatics.biomedcentral.com/)","snPcode":"","submissionUrl":"https://www.editorialmanager.com/binf","title":"BMC Bioinformatics","twitterHandle":"@BMC_Bioinformatics","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"em","reportingPortfolio":"BMC Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"a92ddcfb-e30d-47d5-801d-d7f77ac2111f","owner":[],"postedDate":"March 23rd, 2026","published":true,"recentEditorialEvents":[{"type":"editorInvitedReview","content":"","date":"2026-05-18T11:54:25+00:00","index":31,"fulltext":""},{"type":"reviewerAgreed","content":"71065197978341630602752689837229355354","date":"2026-05-15T10:35:43+00:00","index":30,"fulltext":""},{"type":"reviewersInvited","content":"2","date":"2026-05-15T10:22:41+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-05-15T10:22:13+00:00","index":"","fulltext":""}],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-05-15T10:38:43+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-23 16:11:52","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v2","identity":"rs-4831215","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4831215","identity":"rs-4831215","version":["v2"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}