Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds

スポンサーリンク

概要

• 論文の詳細を見る

• Enumeration of chemical compounds plays a basic role in the design of drugs and the determination of chemical structures from mass spectrometry. Hence, it has been studied by mathematicians and computer scientists as well as chemists for quite a long time. In this technical report, we restrict enumerated structures to trees, and propose efficient algorithms, BfsSimEnum and BfsMulEnum for enumeration of tree-like chemical compounds without and with multiple bonds, respectively. Unlike many existing approaches, our methods iteratively add each atom to a balanced tree by breadth-first search order. In order to reduce large search space, we adjust some important concepts such as left-heavy, center-rooted and normal form to balanced trees. For evaluation of efficiency, we perform experiments for several instances, and compare our methods with existing methods. The results suggest that our proposed methods are exact and more efficient.

• 2013-12-04

著者

• Tatsuya Akutsu

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• Morihiro Hayashida

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Nagamochi Hiroshi

  Kyoto Univ.

• Hiroshi Nakashima

  ACCMS, Kyoto University

• Tatsuya Akutsu

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Tatsuya Akutsu

  Bioinformatics Center Institute For Chemical Research Kyoto Univerty

• Yang Zhao

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Hiroshi Nagamochi

  Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University

• Jira Jindalertudomdee

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

関連論文

• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• RNA-RNA Interaction Prediction Using Integer Programming with Threshold Cut
• Constant Time Generation of Trees with Degree Bounds
• A Quadsection Algorithm for Grammar-Based Image Compression
• Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
• A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
• k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
• Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
• Enumerating Colored and Rooted Outerplanar Graphs
• 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)
• An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
• Orthogonal Drawings for Plane Graphs with Specified Face Areas
• Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
• Symmetry Breaking by Dominance Detection in Distributed Environments
• Conditional Random Field Approach to Prediction of Protein-protein Interactions Using Domain Information
• Integer Programming and Dynamic Programming-based Methods of Optimizing Control Policy in Probabilistic Boolean Networks with Hard Constraints
• An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees
• Around the Constructive Orbit Problem in Distributed Constraint Programming
• The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
• Prediction of protein residue contacts using discriminative random field
• Prediction of protein residue contacts using discriminative random field
• FOREWORD (Special Section on Discrete Mathematics and Its Applications)
• Efficient Computation of Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
• Prediction of RNA Secondary Structures with Binding Sites Using Dynamic Programming Algorithm
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
• Message from the Editor-in-Chief
• Message from the Editor-in-Chief
• Message from the Editor-in-Chief
• Accelerating A* algorithms by sweeping out small-degree nodes
• Protein complex prediction via improved verification methods using constrained domain-domain matching
• Predicting Protein-RNA Residue-base Contacts Using Two-dimensional Conditional Random Field
• Finding Conserved Regions in Protein Structures Using Support Vector Machines and Structure Alignment
• CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
• Inferring Strengths of Protein-Protein Interactions Using Support Vector Regression
• A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
• Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
• Evaluating Effectiveness of Accessibility to Infer RNA-RNA Interactions
• Survival Analysis by Penalized Regression and Matrix Factorization
• A Dominating Set Approach to Structural Controllability of Unidirectional Bipartite Networks
• Prediction of Heterodimeric Protein Complexes from Weighted Protein-Protein Interaction Networks Using Novel Features and Kernel Functions
• Prediction of Heterodimeric Protein Complexes from Weighted Protein-Protein Interaction Networks Using Novel Features and Kernel Functions
• Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
• Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
• Algorithms for Finding a Largest Common Subtree of Bounded Degree
• CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
• Parallelization of Enumerating Tree-like Chemical Compounds by Breadth-first Search Order
• Prediction of Heterotrimeric Protein Complexes by Two-phase Learning Using Neighboring Kernels
• Prediction of Heterotrimeric Protein Complexes by Two-phase Learning Using Neighboring Kernels
• Grammar-based Compression for Multiple Trees Using Integer Programming
• Grammar-based Compression for Multiple Trees Using Integer Programming

もっと見る 閉じる

スポンサーリンク