A Graph-Based Algorithm for Detecting Long Non-Coding RNAs Through RNA Secondary Structure Analysis

Non-coding RNAs (ncRNAs) are involved in many biological processes, making their identification and functional characterization a priority. Among them, long non-coding RNAs (lncRNAs) have been shown to regulate diverse cellular processes, such as cell development, stress response, and transcriptional regulation. The continued identification of new lncRNAs highlights the demand for reliable methods for their detection, with structural analysis offering insightful information. Currently, lncRNAs are identified using tools such as LncFinder, whose database has a large collection of lncRNAs from humans, mice, and chickens, among others. In this work, we present a graph-based algorithm to represent and compare RNA secondary structures. Rooted tree graphs were used to compare two groups of Saccharomyces cerevisiae RNA sequences, lncRNAs and not lncRNAs, by searching for structural similarities between each group. When applied to a novel candidate sequence dataset, the algorithm evaluated whether characteristic structures identified in known lncRNAs recurred. If so, the sequences were classified as likely lncRNAs. These results indicate that graph-based structural analysis offers a complementary methodology for identifying lncRNAs and may complement existing sequence-based tools such as lncFinder or PreLnc. Recent studies have shown that tumor cells can secrete lncRNAs into human biological fluids forming circulating lncRNAs which can be used as biomarkers for cancer. Our algorithm could be applied to identify novel lncRNAs with structural similarities to those associated with tumor malignancy.