Network-Based Structural Alignment of RNA Sequences Using TOPAS

Overview

Journal Methods Mol Biol

Specialty Molecular Biology

Date 2023 Jan 27

PMID 36705903

Authors

Chun-Chi Chen

Hyundoo Jeong

Xiaoning Qian

Byung-Jun Yoon

Affiliations

Soon will be listed here.

Abstract

TOPAS (TOPological network-based Alignment of Structural RNAs) is a network-based alignment algorithm that predicts structurally sound pairwise alignment of RNAs. In order to take advantage of recent advances in comparative network analysis for efficient structurally sound RNA alignment, TOPAS constructs topological network representations for RNAs, which consist of sequential edges connecting nucleotide bases as well as structural edges reflecting the underlying folding structure. Structural edges are weighted by the estimated base-pairing probabilities. Next, the constructed networks are aligned using probabilistic network alignment techniques, which yield a structurally sound RNA alignment that considers both the sequence similarity and the structural similarity between the given RNAs. Compared to traditional Sankoff-style algorithms, this network-based alignment scheme leads to a significant reduction in the overall computational cost while yielding favorable alignment results. Another important benefit is its capability to handle arbitrary folding structures, which can potentially lead to more accurate alignment for RNAs with pseudoknots.

References

Mathews D, Turner D . Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J Mol Biol. 2002; 317(2):191-203. DOI: 10.1006/jmbi.2001.5351. View

Hofacker I, Bernhart S, Stadler P . Alignment of RNA base pairing probability matrices. Bioinformatics. 2004; 20(14):2222-7. DOI: 10.1093/bioinformatics/bth229. View

Havgaard J, Lyngso R, Stormo G, Gorodkin J . Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics. 2005; 21(9):1815-24. DOI: 10.1093/bioinformatics/bti279. View

Gardner P, Wilm A, Washietl S . A benchmark of multiple sequence alignment programs upon structural RNAs. Nucleic Acids Res. 2005; 33(8):2433-9. PMC: 1087786. DOI: 10.1093/nar/gki541. View

Will S, Reiche K, Hofacker I, Stadler P, Backofen R . Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering. PLoS Comput Biol. 2007; 3(4):e65. PMC: 1851984. DOI: 10.1371/journal.pcbi.0030065. View

Harmanci A, Sharma G, Mathews D . PARTS: probabilistic alignment for RNA joinT secondary structure prediction. Nucleic Acids Res. 2008; 36(7):2406-17. PMC: 2367733. DOI: 10.1093/nar/gkn043. View

Fu Y, Sharma G, Mathews D . Dynalign II: common secondary structure prediction for RNA homologs with domain insertions. Nucleic Acids Res. 2014; 42(22):13939-48. PMC: 4267632. DOI: 10.1093/nar/gku1172. View

Will S, Otto C, Miladi M, Mohl M, Backofen R . SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics. Bioinformatics. 2015; 31(15):2489-96. PMC: 4514930. DOI: 10.1093/bioinformatics/btv185. View

Sundfeld D, Havgaard J, de Melo A, Gorodkin J . Foldalign 2.5: multithreaded implementation for pairwise structural RNA alignment. Bioinformatics. 2015; 32(8):1238-40. PMC: 4824132. DOI: 10.1093/bioinformatics/btv748. View

10.

Sharan R, Ideker T . Modeling cellular machinery through biological network comparison. Nat Biotechnol. 2006; 24(4):427-33. DOI: 10.1038/nbt1196. View

11.

Chen C, Jeong H, Qian X, Yoon B . TOPAS: network-based structural alignment of RNA sequences. Bioinformatics. 2019; 35(17):2941-2948. DOI: 10.1093/bioinformatics/btz001. View

12.

Palla G, Derenyi I, Farkas I, Vicsek T . Uncovering the overlapping community structure of complex networks in nature and society. Nature. 2005; 435(7043):814-8. DOI: 10.1038/nature03607. View

13.

Duchenne O, Bach F, Kweon I, Ponce J . A Tensor-Based Algorithm for High-Order Graph Matching. IEEE Trans Pattern Anal Mach Intell. 2011; 33(12):2383-95. DOI: 10.1109/TPAMI.2011.110. View

14.

Jeong H, Liu Z . PRIME: a probabilistic imputation method to reduce dropout effects in single-cell RNA sequencing. Bioinformatics. 2020; 36(13):4021-4029. DOI: 10.1093/bioinformatics/btaa278. View

15.

Jeong H, Khunlertgit N . Effective single-cell clustering through ensemble feature selection and similarity measurements. Comput Biol Chem. 2020; 87:107283. DOI: 10.1016/j.compbiolchem.2020.107283. View

16.

Singh R, Xu J, Berger B . Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc Natl Acad Sci U S A. 2008; 105(35):12763-8. PMC: 2522262. DOI: 10.1073/pnas.0806627105. View

17.

Sahraeian S, Yoon B . SMETANA: accurate and scalable algorithm for probabilistic alignment of large-scale biological networks. PLoS One. 2013; 8(7):e67995. PMC: 3710069. DOI: 10.1371/journal.pone.0067995. View

18.

Huang Q, Wu L, Zhang X . An efficient network querying method based on conditional random fields. Bioinformatics. 2011; 27(22):3173-8. DOI: 10.1093/bioinformatics/btr524. View

19.

Kuchaiev O, Milenkovic T, Memisevic V, Hayes W, Przulj N . Topological network alignment uncovers biological function and phylogeny. J R Soc Interface. 2010; 7(50):1341-54. PMC: 2894889. DOI: 10.1098/rsif.2010.0063. View

20.

Malod-Dognin N, Przulj N . L-GRAAL: Lagrangian graphlet-based network aligner. Bioinformatics. 2015; 31(13):2182-9. PMC: 4481854. DOI: 10.1093/bioinformatics/btv130. View