检索结果-内蒙古大学图书馆

A graph theoretic approach to protein structure selection

ARTIFICIAL INTELLIGENCE IN MEDICINE 2009年第2-3期45卷 229-237页

作者： Vassura, Marco Margara, Luciano Fariselli, Piero Casadio, Rita Univ Bologna Dept Comp Sci I-40127 Bologna Italy Univ Bologna Dept Biol Biocomp Grp I-40127 Bologna Italy

Objective: Protein structure prediction (PSP) aims to reconstruct the 3D structure of a given protein starting from its primary structure (chain of amino acidic residues). It is a well-known fact that the 3D structure of a protein only depends on its primary structure. PSP is one of the most important and still unsolved problems in computational biology. Protein structure selection (PSS), instead of reconstructing a 3D model for the given chain, aims to select among a given, possibly large, number of 3D structures (called decoys) those that are closer (according to a given notion of distance) to the original (unknown) one. In this paper we address PSS problem using graph theoretic techniques. Methods and materials: Existing methods for solving PSS make use of suitably defined energy functions which heavily rely on the primary structure of the protein and on protein chemistry. In this paper we present a new approach to PSS which does not take advantage of the knowledge of the primary structure of the protein but only depends on the graph theoretic properties of the decoys graphs (vertices represent residues and edges represent pairs of residues whose Euclidean distance is less than or equal to a fixed threshold). Results: Even if our methods only rely on approximate geometric information, experimental results show that some of the adopted graph properties score similarly to energy-based filtering functions in selecting the best decoys. Conclusion: Our results highlight the principal role of geometric information in PSS, setting a new starting point and filtering method for existing energy function-based techniques. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Protein structure prediction Protein folding Protein structure selection Contact maps graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A graph-Based Approach to Find Teleconnections in Climate Data

引用

STATISTICAL ANALYSIS AND DATA MINING 2013年第3期6卷 158-179页

作者： Kawale, Jaya Liess, Stefan Kumar, Arjun Steinbach, Michael Snyder, Peter Kumar, Vipin Ganguly, Auroop R. Samatova, Nagiza F. Semazzi, Fredrick Univ Minnesota Dept Comp Sci Minneapolis MN 55455 USA Univ Minnesota Dept Soil Water & Climate St Paul MN 55108 USA Northeastern Univ Civil & Environm Engn Boston MA 02115 USA N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA N Carolina State Univ Dept Marine Earth & Atmospher Sci Raleigh NC 27695 USA

Pressure dipoles are important long distance climate phenomena (teleconnection) characterized by pressure anomalies of the opposite polarity appearing at two different locations at the same time. Such dipoles have been proven important for understanding and explaining the variability in climate in many regions of the world, e.g. the El Nino Southern Oscillation (ENSO) climate phenomenon, which is described by opposite pressure anomalies between the west and east Pacific and is known to be responsible for precipitation and temperature anomalies worldwide. This paper presents a graph-based approach called shared reciprocal nearest neighbor approach that considers only reciprocal positive and negative edges in the shared nearest neighbor graph to find the dipoles. One crucial aspect of our approach to the analysis of such networks is a careful treatment of negative correlations, whose proper consideration is critical for finding the dipoles. Further, our work shows the importance of modeling the time-dependent patterns of the dipoles in a changing climate in order to better capture the impact of important climate phenomena on the globe. To show the utility of finding dipoles using our approach, we show that the data driven dynamic climate indices generated from our algorithm generally perform better than static indices formed from the fixed locations used by climate scientists in terms of capturing impact on global temperature and precipitation. Our approach can generate a single snapshot picture of all the dipole interconnections on the globe in a given dataset and thus makes it possible to study the changes in dipole interactions and movements. As teleconnections are crucial in the understanding of the global climate system, there is a pressing need to better understand the behavior and interactions of these atmospheric processes as well as to capture them precisely. Our systematic graph-based approach to find the teleconnections in climate data is an attempt in that

关键词： graph algorithm teleconnections dipole discovery

来源：评论

学校读者我要写书评

暂无评论

Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 765-770页

作者： Addario-Berry, Louigi Kennedy, W. S. King, Andrew D. Li, Zhentao Reed, Bruce McGill Univ Sch Comp Sci Montreal PQ Canada

An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords;i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete. (c) 2008 Elsevier B.V. All rights reserved.

关键词： graph algorithm Clique-separable graph i-triangulated graph Tree decomposition

来源：评论

学校读者我要写书评

暂无评论

The minimum vulnerability problem on specific graph classes

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期32卷 1288-1304页

作者： Aoki, Yusuke Halldorsson, Bjarni V. Halldorsson, Magnus M. Ito, Takehiro Konrad, Christian Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan JST CREST 4-1-8 Honcho Kawaguchi Saitama 3320012 Japan Reykjavik Univ Sch Comp Sci Menntavegi 1 IS-101 Reykjavik Iceland

Suppose that each edge e of an undirected graph G is associated with three nonnegative integers , and , called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding paths in G between two prescribed vertices with the minimum total cost;each edge e can be shared without any cost by at most paths, and can be shared by more than paths if we pay , but cannot be shared by more than paths even if we pay the cost for e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number of required paths.

关键词： Bounded treewidth graph Chordal graph Fixed parameter tractability graph algorithm Minimum vulnerability problem

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of cliques in a graph

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期333卷 43-58页

作者： Ito, Takehiro Ono, Hirotaka Otachi, Yota Tohoku Univ Grad Sch Informat Sci 6-3-09 AobaAramaki Aza Aoba Ku Sendai 9808579 Japan Nagoya Univ Grad Sch Informat FurochoChikusa Ku Nagoya 4648601 Japan

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques from the viewpoint of polynomial-time solvability. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. Furthermore, we show that the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm Clique

来源：评论

学校读者我要写书评

暂无评论

A TOPOLOGICAL APPROACH TO DYNAMIC graph CONNECTIVITY

引用

INFORMATION PROCESSING LETTERS 1987年第1期25卷 65-70页

作者： REIF, JH HARVARD UNIV DIV APPL SCIAIKEN COMPUTAT LABCAMBRIDGEMA 02138

A dynamic connectivity problem consists of an initial graph, and a sequence of operations consisting of graph modifications and graph connectivity tests. The size n of the problem is the sum of the maximum number of vertices and edges of the derived graph, plus the number of operations to be executed. Each graph modification is a deletion of either an edge or an isolated vertex. Each graph connectivity test is to determine if there exists a path in the current graph between two given vertices (the vertices can vary for distinct tests). The best previously known time for this dynamic connectivity problem was Ω(n 2 ). Our main result is an O(ng+n log n) time algorithm for the dynamic connectivity problem in the case of the maximum genus of the derived graph being g.

关键词： graph algorithm connectivity dynamic algorithm planar graph

来源：评论

学校读者我要写书评

暂无评论

FAST, EFFICIENT PARALLEL algorithmS FOR SOME graph PROBLEMS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1981年第4期10卷 682-691页; 作者： SAVAGE, C JAJA, J UNIV ILLINOIS URBANAIL 61801 UNIV TEXAS ARLINGTONTX 76019 PENN STATE UNIV DEPT COMP SCIUNIVERSITY PKPA 16802; algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity O(log2; algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity $O (\log^{2} n)$; 关键词： parallel algorithm graph algorithm minimum spanning tree biconnected component bridge fundamental cycle computational complexity graph theory multiprocessing; 来源：评论; 学校读者我要写书评

暂无评论

Subgraph isomorphism in graph classes

引用

DISCRETE MATHEMATICS 2012年第21期312卷 3164-3173页

作者： Kijima, Shuji Otachi, Yota Saitoh, Toshiki Uno, Takeaki Kobe Univ Grad Sch Engn Kobe Hyogo 6578501 Japan Kyushu Univ Grad Sch Informat Sci & Elect Engn Fukuoka 8190395 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Natl Inst Informat Tokyo 1018430 Japan

We investigate the computational complexity of the following restricted variant of SUBgraph ISOMORPHISM: given a pair of connected graphs G = (V-G, E-G) and H = (V-H, E-H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of SUBgraph ISOMORPHISM such as HAMILTONIAN PATH, CLIQUE, BANDWIDTH, and graph ISOMORPHISM can be solved in polynomial time, while these problems are hard in general. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Subgraph isomorphism graph class NP-completeness graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Maintaining the classes of 4-edge-connectivity in a graph on-line

引用

algorithmICA 1998年第3期20卷 242-276页

作者： Dinitz, Y Westbrook, J Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel AT&T Bell Labs Res Florham Pk NJ 07932 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA

Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k-edge-connectivity or k-edge-connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and it Insert-Vertex and lit Insert-Edge updates can be performed in O(q + m + ii log n total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity (k arbitrary) in a (k-1)-edge-connected graph is presented. Its complexity is O(q + m + n). with O(M + k(2)n log(n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices.

关键词： dynamic algorithm dynamic data structure graph algorithm edge-connectivity connectivity class component analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Automata for the verification of monadic second-order graph properties

引用

JOURNAL OF APPLIED LOGIC 2012年第4期10卷 368-409页

作者： Courcelle, Bruno Durand, Irene Univ Bordeaux Labri CNRS F-33405 Talence France

The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite automata from monadic second-order sentences. These automata recognize the terms over fixed finite signatures that define graphs satisfying the given sentences. However, this construction produces automata of hyper-exponential sizes, and is thus impossible to use in practice in many cases. To overcome this difficulty, we propose to specify the transitions of automata by programs instead of tables. Such automata are called fly-automata. By using them, we can check certain monadic second-order graph properties with limited quantifier alternation depth, that are nevertheless interesting for graph Theory. We give explicit constructions of automata relative to graphs of bounded clique-width, and we report on experiments. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithm Automaton Monadic second-order logic Clique-width Fixed-parameter tractability Fly-automaton

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法