Parallelization of Enumerating Tree-like Chemical Compounds by Breadth-first Search Order
スポンサーリンク
概要
- 論文の詳細を見る
Enumerating chemical compounds greatly assists designing drugs and determining chemical structures from mass spectrometry. In our previous study, we developed efficient algorithms, BfsSimEnum and BfsMulEnum for enumerating tree-like chemical compounds without and with multiple bonds, respectively. In this technical report, we develop a parallelized algorithm BfsEnumP by modifying BfsSimEnum in a simple manner to further reduce execution time. BfsSimEnum constructs a family tree in which each node denotes a molecular tree. BfsEnumP divides the family tree at some depth, and each subtree to be constructed is assigned to a processor. For evaluation, we perform experiments for several instances with varying the division depth and the number of processors, and show that it achieves about 80% parallelization efficiency.
- 2014-02-24
著者
-
Tatsuya Akutsu
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Morihiro Hayashida
Bioinformatics Center Institute For Chemical Research 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
-
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
- A Quadsection Algorithm for Grammar-Based Image Compression
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- 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
- Prediction of protein residue contacts using discriminative random field
- Prediction of protein residue contacts using discriminative random field
- 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
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- 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
- Inferring Strengths of Protein-Protein Interactions Using Support Vector Regression
- 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
- 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