Alignments of biomolecular contact maps. Issue 4 (11th June 2021)

• Record Type: Journal Article
• Authors: Stadler, Peter F.
• Is Part Of: Interface focus. Volume 11:Issue 4(2021)
• Publication Date: 2021-06-11
• Subjects: graph comparison -- super-structure -- RNA secondary structure -- dynamic programming; Physical sciences -- Periodicals; Life sciences -- Periodicals; 500
• DOI: 10.1098/rsfs.2020.0066
• Languages: English
• ISSNs: 2042-8898

Abstract

Abstract : Alignments of discrete objects can be constructed in a very general setting as super-objects from which the constituent objects are recovered by means of projections. Here, we focus on contact maps, i.e. undirected graphs with an ordered set of vertices. These serve as natural discretizations of RNA and protein structures. In the general case, the alignment problem for vertex-ordered graphs is NP-complete. In the special case of RNA secondary structures, i.e. crossing-free matchings, however, the alignments have a recursive structure. The alignment problem then can be solved by a variant of the Sankoff algorithm in polynomial time. Moreover, the tree or forest alignments of RNA secondary structure can be understood as the alignments of ordered edge sets.