Hiroshi Nagamochi

Hiroshi Nagamochi

orcid

Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
18 March 2005 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
HNHiroshi Nagamochi
Hiroshi Nagamochi

14 August 2021 in Algorithms for Molecular Biology
Verified
Journal Article
Open access
PDF file
NANaveed Ahmed Azam
Naveed Ahmed Azam
JZJianshen Zhu
Jianshen Zhu
YSYanming Sun
Yanming Sun
YSYu Shi
Yu Shi
ASAleksandar Shurbevski
Aleksandar Shurbevski
Tatsuya AkutsuTatsuya Akutsu
Tatsuya Akutsu
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$$n=40 , whereas graphs can be enumerated for up to $$n=15$$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$$n=50 and diameter 30.

1 April 2008 in Algorithmica
Verified
Journal Article
Closed access
PDF file
HNHiroshi Nagamochi
Hiroshi Nagamochi

1 January 2010 in Journal of Advanced Mechanical Design, Systems, and Manufacturing
Verified
Journal Article
Open access
YKYoshiyuki Karuno
Yoshiyuki Karuno
HNHiroshi Nagamochi
Hiroshi Nagamochi
XWXiaoming Wang
Xiaoming Wang

Verified
Journal Article
Open access
PDF file
YSYu Shi
Yu Shi
JZJianshen Zhu
Jianshen Zhu
Naveed AzamNaveed Azam
Naveed Azam
KHKazuya Haraguchi
Kazuya Haraguchi
Liang ZhaoLiang Zhao
Liang Zhao
Tatsuya AkutsuTatsuya Akutsu
Tatsuya Akutsu
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.

30 May 2014 in Journal of Cheminformatics
Verified
Journal Article
Open access
PDF file
MSMasaki Suzuki
Masaki Suzuki
HNHiroshi Nagamochi
Hiroshi Nagamochi
Tatsuya AkutsuTatsuya Akutsu
Tatsuya Akutsu
Background The enumeration of chemical graphs (molecular graphs) satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics because it leads to a variety of useful applications including structure determination and development of novel chemical compounds. Results We consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds. Conclusions We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently.