RNA graph partitioning for the discovery of RNA modularity: a novel application of graph partition algorithm to biology.
RNA graph partitioning for the discovery of RNA modularity: a novel application of graph partition algorithm to biology.
复制标题
DOI：
10.1371/journal.pone.0106074
复制
发表时间：
2014
期刊：
影响因子：
3.7
通讯作者：
Schlick T
中科院分区：
文献类型：
--
作者：
Kim N;Zheng Z;Elmetwaly S;Schlick T
图表示已被广泛用于分析和设计各种经济，社会，军事，政治和生物网络。在系统生物学中，细胞和器官的网络对于理解疾病和医学治疗是有用的，在结构生物学中，可以描述分子的结构，包括RNA结构。在我们的RNA-As-Graphs（RAG）框架中，我们将RNA结构表示为树形图，将不成对的区域转换为顶点，将螺旋转换为边。在这里，我们探讨了RNA结构的模块化应用图论中已知的图划分划分到子图的RNA图。据我们所知，这是第一次将图划分应用于生物学，其结果表明了一般模块化设计的系统方法。图划分算法利用拉普拉斯特征向量（μ2）的数学性质，其对应于与定义图的拓扑矩阵相关联的第二特征值（λ2）：λ2描述了整个拓扑，并且μ2的分量之和为零。这三种类型的算法，称为中位数，符号和间隙切割，通过分别确定μ2分量的中位数，零和最大间隙的切割节点来划分图。我们将这些算法应用于45个图，对应于所有解决的RNA结构，通过11个顶点（约220个核苷酸）。当我们观察到中位割将图划分为两个大小相似的子图时，符号割和间隙割将图划分为两个拓扑不同的子图。我们发现，差距切割对RNA产生了最佳的生物相关分配，因为它使RNA在不太稳定的连接处分裂，同时保持连接的完整。迭代缺口切割建议设计大RNA结构的基本模块和组装协议。因此，我们的图子结构提出了一个系统的方法来探索生物网络的模块化。在我们对RNA结构的应用中，子图也提出了新的RNA基序的设计策略。
Graph representations have been widely used to analyze and design various economic, social, military, political, and biological networks. In systems biology, networks of cells and organs are useful for understanding disease and medical treatments and, in structural biology, structures of molecules can be described, including RNA structures. In our RNA-As-Graphs (RAG) framework, we represent RNA structures as tree graphs by translating unpaired regions into vertices and helices into edges. Here we explore the modularity of RNA structures by applying graph partitioning known in graph theory to divide an RNA graph into subgraphs. To our knowledge, this is the first application of graph partitioning to biology, and the results suggest a systematic approach for modular design in general. The graph partitioning algorithms utilize mathematical properties of the Laplacian eigenvector (µ2) corresponding to the second eigenvalues (λ2) associated with the topology matrix defining the graph: λ2 describes the overall topology, and the sum of µ2′s components is zero. The three types of algorithms, termed median, sign, and gap cuts, divide a graph by determining nodes of cut by median, zero, and largest gap of µ2′s components, respectively. We apply these algorithms to 45 graphs corresponding to all solved RNA structures up through 11 vertices (∼220 nucleotides). While we observe that the median cut divides a graph into two similar-sized subgraphs, the sign and gap cuts partition a graph into two topologically-distinct subgraphs. We find that the gap cut produces the best biologically-relevant partitioning for RNA because it divides RNAs at less stable connections while maintaining junctions intact. The iterative gap cuts suggest basic modules and assembly protocols to design large RNA structures. Our graph substructuring thus suggests a systematic approach to explore the modularity of biological networks. In our applications to RNA structures, subgraphs also suggest design strategies for novel RNA motifs.
登录
查看更多内容
影响因子：
3
作者：
Izzo JA;Kim N;Elmetwaly S;Schlick T
通讯作者：
Schlick T
影响因子：
--
作者：
Leontis, Neocles B;Westhof, Eric
通讯作者：
Westhof, Eric
影响因子：
64.5
作者：
Kalir, S;Alon, U
通讯作者：
Alon, U
影响因子：
38.3
作者：
通讯作者：
--
影响因子：
3
作者：
Haynes, T;Knisley, D;Seier, E;Zou, Y
通讯作者：
Zou, Y