A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
スポンサーリンク
概要
- 論文の詳細を見る
This paper proposes a novel clustering method based on graph theory for analysis of biological networks. In this method, each biological network is treated as an undirected graph and edges are weighted based on sililarities of nodes. Then, maximal components, which are defined based on edge connectivity, are computed and the nodes are partitioned into clusters by selecting disjoint maximal components. The proposed method was applied to clustering of protein sequences and was compared with conventional clustering methods. The obtained clusters were evaluated using P-values for GO (GeneOntology) terms. The average P-values for the proposed method were better than those for other methods.
- 一般社団法人情報処理学会の論文
- 2008-03-15
著者
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
Hayashida Morihiro
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Akutsu Tatsuya
Kyoto Univ. Kyoto‐shi Jpn
-
Akutsu Tatsuya
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Engineering Kyoto University
-
Nagamochi Hiroshi
Dep. Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto Univ.
-
Hayashida Morihiro
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
-
Akutsu Tatsuya
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
関連論文
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
- Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences(Discrete Mathematics and Its Applications)
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (Special Issue on Selected Papers from LA Symposium)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex(Graph Algorithms,Foundations of Computer Science)
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- Approximating a Generalization of Metric TSP(Graph Algorithms,Foundations of Computer Science)
- Approximation to the Minimum Cost Edge Installation Problem
- Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints(Discrete Mathematics and Its Applications)
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- Worst Case Analysis for Pickup and Delivery Problems with Transfer
- Orthogonal Drawings for Plane Graphs with Specified Face Areas(Theory of Computer Science and Its Applications)
- 1A2 AN IMPROVED APPROXIMATION ALGORITHM FOR CAPACITATED MULTICAST ROUTINGS IN NETWORKS(Technical session 1A: Combinatorial optimization)
- 5B2 AN ITERATED LOCAL SEARCH ALGORITHM BASED ON NONLINEAR PROGRAMMING FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- 2B1 A DP-BASED HEURISTIC ALGORITHM FOR THE DISCRETE SPLIT DELIVERY VEHICLE ROUTING PROBLEM(Technical session 2B: Vehicle scheduling and communication)
- A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs(Discrete Mathematics and Its Applications)
- A Note on Approximating the Survivable Network Design Problem in Hypergraphs(Special Issue on Selected Papers from LA Symposium)
- Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(Discrete Mathematics and Its Applications)
- A Fast Algorithm for Cactus Representations of Minimum Cuts
- Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree (Special Section on Discrete Mathematics and Its Applications)
- Hardness Results on Local Multiple Alignment of Biological Sequences
- 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- Approximability of the Minimum Maximal Matching Problem in Planar Graphs(Graphs and Networks)
- An Approximation of the Minimum Vertex Cover in a Graph
- Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
- Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
- Approximating the Minmax Rooted-Subtree Cover Problem(Graphs and Networks)
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Hardness Results on Local Multiple Alignment of Biological Sequences
- Kernel Methods for Chemical Compounds: From Classification to Design
- Conservation Laws and Symmetries in Competitive Systems
- Measuring the Similarity of Protein Structures Using Image Compression Algorithms
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- An Efficient Method of Computing Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
- Conservation Laws and Symmetries in Competitive Systems
- Integer Programming-Based Approach to Attractor Detection and Control of Boolean Networks
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors
- 4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)
- 5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems)
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines
- A DP-based Heuristic Algorithm for the Discrete Split Delivery Vehicle Routing Problem