Format

Send to

Choose Destination
J Chem Inf Model. 2017 May 22;57(5):1045-1054. doi: 10.1021/acs.jcim.6b00546. Epub 2017 May 3.

ArbAlign: A Tool for Optimal Alignment of Arbitrarily Ordered Isomers Using the Kuhn-Munkres Algorithm.

Author information

1
Dean's Office, College of Arts and Sciences, and Department of Chemistry, Bucknell University , Lewisburg, Pennsylvania 17837, United States.
2
Department of Mathematical Sciences, Susquehanna University , Selinsgrove, Pennsylvania 17870, United States.
3
Lewisburg Area High School , Lewisburg, Pennsylvania 17837, United States.

Abstract

When assessing the similarity between two isomers whose atoms are ordered identically, one typically translates and rotates their Cartesian coordinates for best alignment and computes the pairwise root-mean-square distance (RMSD). However, if the atoms are ordered differently or the molecular axes are switched, it is necessary to find the best ordering of the atoms and check for optimal axes before calculating a meaningful pairwise RMSD. The factorial scaling of finding the best ordering by looking at all permutations is too expensive for any system with more than ten atoms. We report use of the Kuhn-Munkres matching algorithm to reduce the cost of finding the best ordering from factorial to polynomial scaling. That allows the application of this scheme to any arbitrary system efficiently. Its performance is demonstrated for a range of molecular clusters as well as rigid systems. The largely standalone tool is freely available for download and distribution under the GNU General Public License v3.0 (GNU_GPL_v3) agreement. An online implementation is also provided via a web server ( http://www.arbalign.org ) for convenient use.

PMID:
28398732
DOI:
10.1021/acs.jcim.6b00546
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for American Chemical Society
Loading ...
Support Center