title: An efficient algorithm for planar drawing of RNA structures with pseudoknots of any type.
abstract: An RNA pseudoknot is a tertiary structural element in which bases of a loop pair with complementary bases are outside the loop. A drawing of RNA secondary structures is a tree, but a drawing of RNA pseudoknots is a graph that has an inner cycle within a pseudoknot and possibly outer cycles formed between the pseudoknot and other structural elements. Visualizing a large-scale RNA structure with pseudoknots as a planar drawing is challenging because a planar drawing of an RNA structure requires both pseudoknots and an entire structure enclosing the pseudoknots to be embedded into a plane without overlapping or crossing. This paper presents an efficient heuristic algorithm for visualizing a pseudoknotted RNA structure as a planar drawing. The algorithm consists of several parts for finding crossing stems and page mapping the stems, for the layout of stem-loops and pseudoknots, and for overlap detection between structural elements and resolving it. Unlike previous algorithms, our algorithm generates a planar drawing for a large RNA structure with pseudoknots of any type and provides a bracket view of the structure. It generates a compact and aesthetic structure graph for a large pseudoknotted RNA structure in O([Formula: see text]) time, where n is the number of stems of the RNA structure.
authors.affiliation: 1 Department of Computer Science and Engineering, Inha University, Incheon 402-751, Korea.
authors.forename: Yanga
authors.initials: Y
authors.lastname: Byun
authors.affiliation: 1 Department of Computer Science and Engineering, Inha University, Incheon 402-751, Korea.
authors.forename: Kyungsook
authors.initials: K
authors.lastname: Han
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*
chemical_list: D012313:RNA
keywords: RNA secondary structure; algorithm; planar drawing; pseudoknot; visualization