Hiroshi Nagamochi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Hiroshi Nagamochi has a total of 46 co-authors. Here are the top co-authors by number of shared publications:
- Aleksandar Shurbevski
Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan
12 shared publications - Seok-Hee Hong
University of Sydney Australia
12 shared publications - Mingyu Xiao
University of Electronic Science and Technology of China, Chengdu, China
11 shared publications - Tatsuya Akutsu
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto, Japan
11 shared publications - Naveed Ahmed Azam
Department of Mathematics, Quaid-i-Azam University, Islamabad, Pakistan
8 shared publications - Kazuya Haraguchi
Kyoto University
6 shared publications
Latest Publications
- 20 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 21 (5) , 1529-1541
Molecular Design Based on Integer Programming and Splitting Data Sets by Hyperplanes
A novel framework for designing the molecular structure of chemical compounds with a desired chemical property has recently been proposed. The framework infers a desired chemical graph by solving a mixed integer linear program (MILP) that simulates the computation process of two functions: a feature function defined by a two-layered model on chemical graphs and a prediction function constructed by a machine learning method. To improve the learning performance of prediction functions in the framework, we design a method that splits a given data set $\mathcal {C}$ into two subsets $\mathcal {C}^{(i)},i=1,2$ by a hyperplane in a chemical space so that most compounds in the first (resp., second) subset have observed values lower (resp., higher) than a threshold $\theta$ . We construct a prediction function $\psi$ to the data set $\mathcal {C}$ by combining prediction functions $\psi _{i},i=1,2$ each of which is constructed on $\mathcal {C}^{(i)}$ independently. The results of our computational experiments suggest that the proposed method improved the learning performance for several chemical properties to which a good prediction function has been difficult to construct.
- 20 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 21 (5) , 1529-1541
Molecular Design Based on Integer Programming and Splitting Data Sets by Hyperplanes
A novel framework for designing the molecular structure of chemical compounds with a desired chemical property has recently been proposed. The framework infers a desired chemical graph by solving a mixed integer linear program (MILP) that simulates the computation process of two functions: a feature function defined by a two-layered model on chemical graphs and a prediction function constructed by a machine learning method. To improve the learning performance of prediction functions in the framework, we design a method that splits a given data set $\mathcal {C}$ into two subsets $\mathcal {C}^{(i)},i=1,2$ by a hyperplane in a chemical space so that most compounds in the first (resp., second) subset have observed values lower (resp., higher) than a threshold $\theta$ . We construct a prediction function $\psi$ to the data set $\mathcal {C}$ by combining prediction functions $\psi _{i},i=1,2$ each of which is constructed on $\mathcal {C}^{(i)}$ independently. The results of our computational experiments suggest that the proposed method improved the learning performance for several chemical properties to which a good prediction function has been difficult to construct.
- Open Access
- 25 March 2022
- Published by Springer Nature in Applied Intelligence
- Vol. 52 (15) , 17058-17072
A new approach to the design of acyclic chemical compounds using skeleton trees and integer linear programming
Intelligent systems are applied in a wide range of areas, and computer-aided drug design is a highly important one. One major approach to drug design is the inverse QSAR/QSPR (quantitative structure-activity and structure-property relationship), for which a method that uses both artificial neural networks (ANN) and mixed integer linear programming (MILP) has been proposed recently. This method consists of two phases: a forward prediction phase, and an inverse, inference phase. In the prediction phase, a feature function f over chemical compounds is defined, whereby a chemical compound G is represented as a vector f(G) of descriptors. Following, for a given chemical property $$\pi$$ , using a dataset of chemical compounds with known values for property $$\pi$$ , a regressive prediction function $$\psi$$ is computed by an ANN. It is desired that $$\psi (f(G))$$ takes a value that is close to the true value of property $$\pi$$ for the compound G for many of the compounds in the dataset. In the inference phase, one starts with a target value $$y^*$$ of the chemical property $$\pi$$ , and then a chemical structure $$G^*$$ such that $$\psi (f(G^*))$$ is within a certain tolerance level of $$y^*$$ is constructed from the solution to a specially formulated MILP. This method has been used for the case of inferring acyclic chemical compounds. With this paper, we propose a new concept on acyclic chemical graphs, called a skeleton tree, and based on it develop a new MILP formulation for inferring acyclic chemical compounds. Our computational experiments indicate that our newly proposed method significantly outperforms the existing method when the diameter of graphs is up to 8. In a particular example where we inferred acyclic chemical compounds with 38 non-hydrogen atoms from the set {C, O, S} times faster.- 25 March 2022
- Published by Springer Nature in Applied Intelligence
- Vol. 52 (15) , 17058-17072
Open AccessA new approach to the design of acyclic chemical compounds using skeleton trees and integer linear programming
Intelligent systems are applied in a wide range of areas, and computer-aided drug design is a highly important one. One major approach to drug design is the inverse QSAR/QSPR (quantitative structure-activity and structure-property relationship), for which a method that uses both artificial neural networks (ANN) and mixed integer linear programming (MILP) has been proposed recently. This method consists of two phases: a forward prediction phase, and an inverse, inference phase. In the prediction phase, a feature function f over chemical compounds is defined, whereby a chemical compound G is represented as a vector f(G) of descriptors. Following, for a given chemical property $$\pi$$ , using a dataset of chemical compounds with known values for property $$\pi$$ , a regressive prediction function $$\psi$$ is computed by an ANN. It is desired that $$\psi (f(G))$$ takes a value that is close to the true value of property $$\pi$$ for the compound G for many of the compounds in the dataset. In the inference phase, one starts with a target value $$y^*$$ of the chemical property $$\pi$$ , and then a chemical structure $$G^*$$ such that $$\psi (f(G^*))$$ is within a certain tolerance level of $$y^*$$ is constructed from the solution to a specially formulated MILP. This method has been used for the case of inferring acyclic chemical compounds. With this paper, we propose a new concept on acyclic chemical graphs, called a skeleton tree, and based on it develop a new MILP formulation for inferring acyclic chemical compounds. Our computational experiments indicate that our newly proposed method significantly outperforms the existing method when the diameter of graphs is up to 8. In a particular example where we inferred acyclic chemical compounds with 38 non-hydrogen atoms from the set {C, O, S} times faster. - 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1279-1315
Enumeration of Support-Closed Subsets in Confluent Systems
- 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1279-1315
Enumeration of Support-Closed Subsets in Confluent Systems
- 1 November 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 892, 132-154
Re-embedding a 1-plane graph for a straight-line drawing in linear time
- 1 November 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 892, 132-154
Re-embedding a 1-plane graph for a straight-line drawing in linear time
- 1 November 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 303, 171-185
A method for enumerating pairwise compatibility graphs with a given number of vertices
- 1 November 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 303, 171-185
A method for enumerating pairwise compatibility graphs with a given number of vertices
- 14 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 19 (6) , 3233-3245
A Novel Method for Inferring Chemical Compounds With Prescribed Topological Substructures Based on Integer Programming
Drug discovery is one of the major goals of computational biology and bioinformatics. A novel framework has recently been proposed for the design of chemical graphs using both artificial neural networks (ANNs) and mixed integer linear programming (MILP). This method consists of a prediction phase and an inverse prediction phase. In the first phase, an ANN is trained using data on existing chemical compounds. In the second phase, given a target chemical property, a feature vector is inferred by solving an MILP formulated from the trained ANN and then a set of chemical structures is enumerated by a graph enumeration algorithm. Although exact solutions are guaranteed by this framework, the types of chemical graphs have been restricted to such classes as trees, monocyclic graphs and graphs with a specified polymer topology with cycle index up to 2. To overcome the limitation on the topological structure, we propose a new flexible modeling method to the framework so that we can specify a topological substructure of graphs and a partial assignment of chemical elements and bond-multiplicity to a target graph. The results of computational experiments suggest that the proposed system can infer chemical graphs with around up to 50 non-hydrogen atoms.
- 14 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 19 (6) , 3233-3245
A Novel Method for Inferring Chemical Compounds With Prescribed Topological Substructures Based on Integer Programming
Drug discovery is one of the major goals of computational biology and bioinformatics. A novel framework has recently been proposed for the design of chemical graphs using both artificial neural networks (ANNs) and mixed integer linear programming (MILP). This method consists of a prediction phase and an inverse prediction phase. In the first phase, an ANN is trained using data on existing chemical compounds. In the second phase, given a target chemical property, a feature vector is inferred by solving an MILP formulated from the trained ANN and then a set of chemical structures is enumerated by a graph enumeration algorithm. Although exact solutions are guaranteed by this framework, the types of chemical graphs have been restricted to such classes as trees, monocyclic graphs and graphs with a specified polymer topology with cycle index up to 2. To overcome the limitation on the topological structure, we propose a new flexible modeling method to the framework so that we can specify a topological substructure of graphs and a partial assignment of chemical elements and bond-multiplicity to a target graph. The results of computational experiments suggest that the proposed system can infer chemical graphs with around up to 50 non-hydrogen atoms.
- 1 September 2021
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 44 (4) , 2871-2892
On the enumeration of minimal non-pairwise compatibility graphs
- 1 September 2021
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 44 (4) , 2871-2892
On the enumeration of minimal non-pairwise compatibility graphs
- Open Access
- 14 August 2021
- Published by Springer Nature in Algorithms for Molecular Biology
- Vol. 16 (1) , 1-39
A novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming
Analysis of chemical graphs is becoming a major research topic in computational molecular biology due to its potential applications to drug design. One of the major approaches in such a study is inverse quantitative structure activity/property relationship (inverse QSAR/QSPR) analysis, which is to infer chemical structures from given chemical activities/properties. Recently, a novel two-phase framework has been proposed for inverse QSAR/QSPR, where in the first phase an artificial neural network (ANN) is used to construct a prediction function. In the second phase, a mixed integer linear program (MILP) formulated on the trained ANN and a graph search algorithm are used to infer desired chemical structures. The framework has been applied to the case of chemical compounds with cycle index up to 2 so far. The computational results conducted on instances withnnon-hydrogen atoms show that a feature vector can be inferred by solving an MILP for up to $$n=40$$ , whereas graphs can be enumerated for up to $$n=15$$ . When applied to the case of chemical acyclic graphs, the maximum computable diameter of a chemical structure was up to 8. In this paper, we introduce a new characterization of graph structure, called “branch-height” based on which a new MILP formulation and a new graph search algorithm are designed for chemical acyclic graphs. The results of computational experiments using such chemical properties as octanol/water partition coefficient, boiling point and heat of combustion suggest that the proposed method can infer chemical acyclic graphs with around $$n=50$$ and diameter 30.- 14 August 2021
- Published by Springer Nature in Algorithms for Molecular Biology
- Vol. 16 (1) , 1-39
Open AccessA novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming
Analysis of chemical graphs is becoming a major research topic in computational molecular biology due to its potential applications to drug design. One of the major approaches in such a study is inverse quantitative structure activity/property relationship (inverse QSAR/QSPR) analysis, which is to infer chemical structures from given chemical activities/properties. Recently, a novel two-phase framework has been proposed for inverse QSAR/QSPR, where in the first phase an artificial neural network (ANN) is used to construct a prediction function. In the second phase, a mixed integer linear program (MILP) formulated on the trained ANN and a graph search algorithm are used to infer desired chemical structures. The framework has been applied to the case of chemical compounds with cycle index up to 2 so far. The computational results conducted on instances withnnon-hydrogen atoms show that a feature vector can be inferred by solving an MILP for up to $$n=40$$ , whereas graphs can be enumerated for up to $$n=15$$ . When applied to the case of chemical acyclic graphs, the maximum computable diameter of a chemical structure was up to 8. In this paper, we introduce a new characterization of graph structure, called “branch-height” based on which a new MILP formulation and a new graph search algorithm are designed for chemical acyclic graphs. The results of computational experiments using such chemical properties as octanol/water partition coefficient, boiling point and heat of combustion suggest that the proposed method can infer chemical acyclic graphs with around $$n=50$$ and diameter 30. - 9 August 2021
- Published by Springer Nature
- p. 628-644
An Inverse QSAR Method Based on Decision Tree and Integer Programming
- 9 August 2021
- Published by Springer Nature
- p. 628-644
An Inverse QSAR Method Based on Decision Tree and Integer Programming
- Open Access
- 11 March 2021
- Published by MDPI AG in International Journal of Molecular Sciences
- Vol. 22 (6) , 2847
An Inverse QSAR Method Based on a Two-Layered Model and Integer Programming
A novel framework for inverse quantitative structure–activity relationships (inverse QSAR) has recently been proposed and developed using both artificial neural networks and mixed integer linear programming. However, classes of chemical graphs treated by the framework are limited. In order to deal with an arbitrary graph in the framework, we introduce a new model, called a two-layered model, and develop a corresponding method. In this model, each chemical graph is regarded as two parts: the exterior and the interior. The exterior consists of maximal acyclic induced subgraphs with bounded height, the interior is the connected subgraph obtained by ignoring the exterior, and the feature vector consists of the frequency of adjacent atom pairs in the interior and the frequency of chemical acyclic graphs in the exterior. Our method is more flexible than the existing method in the sense that any type of graphs can be inferred. We compared the proposed method with an existing method using several data sets obtained from PubChem database. The new method could infer more general chemical graphs with up to 50 non-hydrogen atoms. The proposed inverse QSAR method can be applied to the inference of more general chemical graphs than before.
- 11 March 2021
- Published by MDPI AG in International Journal of Molecular Sciences
- Vol. 22 (6) , 2847
Open AccessAn Inverse QSAR Method Based on a Two-Layered Model and Integer Programming
A novel framework for inverse quantitative structure–activity relationships (inverse QSAR) has recently been proposed and developed using both artificial neural networks and mixed integer linear programming. However, classes of chemical graphs treated by the framework are limited. In order to deal with an arbitrary graph in the framework, we introduce a new model, called a two-layered model, and develop a corresponding method. In this model, each chemical graph is regarded as two parts: the exterior and the interior. The exterior consists of maximal acyclic induced subgraphs with bounded height, the interior is the connected subgraph obtained by ignoring the exterior, and the feature vector consists of the frequency of adjacent atom pairs in the interior and the frequency of chemical acyclic graphs in the exterior. Our method is more flexible than the existing method in the sense that any type of graphs can be inferred. We compared the proposed method with an existing method using several data sets obtained from PubChem database. The new method could infer more general chemical graphs with up to 50 non-hydrogen atoms. The proposed inverse QSAR method can be applied to the inference of more general chemical graphs than before.