Subject: Summary: Topological indices

From: [email-masked] (Thomas Wieland)
Date: Fri, 18 Aug 95 09:00:43 +0200

Dear Netters,

here is my summary for my recent question on software for topological
indices.
It took some time because two weeks ago the mainboard of my computer was stolen
such that I didn't have access tothe data on my hard disk (meanwhile I got a 
new one).  Furthermore I have to admit that I hadn't remembered that the same
question had been posted this spring (by "Richard Bone" <[email-masked]> on 
22 May 1995 14:45:43 - look for it in CCL archive). The inquiries I received
show, however, that the need for information on this topic is not fulfilled yet.

Thanks to all scientists who answered. My special thank are due to Dr. S. Basak 
of Resource Institute, Dulluth, MN, who even sent me a pile of (p)reprints of 
his works with a lot of valuable information and useful references.

It turned out that there is excellent software available - but not public 
domain. Some simple connectivity or distance indices are certainly not hard to
implement and can be looked up in a large number of publications. But some more 
efforts are needed to program more complex indices.

Best regards,

Th. Wieland

Thomas Wieland               +---------------+
Dipl. Math.                  |+----    +----+|
Lehrstuhl II f. Mathematik   |\    \   |    ||
Universitaet Bayreuth        | \    \  |    ||
                             |  \    \ |    ||
95440 Bayreuth               |   \    \\    ||
Germany                      |    \    \\   ||
Tel. +49 (921) 553386        |     \     \\ ||
Fax  +49 (921) 553385        |      \-------||
                             +---------------+
------------------------------------------------------------------------------

Original question was:

>Dear Colleagues,
>
>I am looking for some simple programs (preferably public-domain,
>best with sources) that are able to compute topological indices
>of molecular graphs, no matter which (Wiener-Index, Randic-Index
>etc.)
>
>I would gratefully appreciate any hints to ftp-sites where such software
>can be found. I tried some WWW-search machines but my key words "topological
>index" didn't suffice.
>
------------------------------------------------------------------------------

From: Lipkowitz <[email-masked]>

A great list of programs for computational chemistry is in each Appendix of
Reviews in Computational Chemistry, VCH Publishers Inc. The list is prepared by
Don Boyd and I'm sure has what you're looking for. Kenny
------------------------------------------------------------------------------

From: "Dr. Subhash Basak" <[email-masked]>

Thank you for your inquiry.  We have two programs, POLLY and APPROBE which 
are currently being used by companies like Upjohn, Glaxo, Government 
agencies like U S Environmental Protection Agency, National Institutes of 
Health, US Army for molecular design and QSAR analysis pertaining to health 
and environment.

I am sending you info about POLLY AND APPROBE below.  I am also mailing you 
a collection of my papers in the area of development of topological indices 
and their applications in QSAR and quantifications of molecular similarity 
as well as applications of similarity in estimating properties of molecules.

The POLLY software is copyright of the University of Minnesota.  Licensing/
ordering information regarding POLLY can be obtained from Bob Hicks of the 
Office of Research and Technology Transfer Administration (ORTTA) of the U 
of Minnesota.  Bob can be reached at: [email-masked].

The price of the software is $2,000.00 (two thousand dollars only) per 
licensed site.  Mr. Hicks can give you more details about the licensing 
aspects.

POLLY v. 2.3

S.C. Basak

Natural Resources Research Institute
University of Minnesota
Duluth, Minnesota 55811
USA

D.K. Harriss
V.R. Magnuson

Department of Chemistry
University of Minnesota
Duluth, Minnesota 55812
USA

!Copyright (C) 1986, 1988 Regents of the University of Minnesota. 
All Rights
Reserved.
I. Introduction

      POLLY is a tested and documented computer program which
calculates the
values of 98 topological (graph theoretic, connectivity and
complexity type) indices for
molecules containing up to 120 atoms composed of the following atom
types:  carbon,
nitrogen, oxygen, chlorine, bromine, sulfur, fluorine, phosphorous,
iodine, boron and
hydrogen.
      These indices include the Zagreg group indices1 , Wiener
index2, Randic's
connectivity index3, higher order connectivity indices and valence
connectivity indices
of different types4, bonding connectivity indices5, information
theoretic indices based
on distance matrix6, indices of neighborhood symmetry7,8,
information theoretic indices
of degree complexity, distance complexity and vertex complexity9,
information theoretic
indices on graph orbits10, and paths of different lengths.
      Topological indices have been successfully used in the
quantification of
molecular similarity5, 11-15, structure-property
correlations2-4,16-19, and prediction of
biomedicinal and toxic properties of different classes of
molecules4,7,8,20.
      The program is structured to accept molecular descriptions in
the form of
SMILES notation but is easily adapted to other, user oriented,
forms of input such as
MOLFILE.  The output consists of values of the 98 indices for each
molecule.
      POLLY is programmed in ANSI C and has been tested on UNIX and
MSDOS
platforms.  POLLY is provided in source code form only on UNIX
platforms, both
source and executable for the MSDOS platform.

II. Running POLLY

      POLLY may be run in either interactive (input from the
keyboard) or
batch (input from a file) modes.  To enter input from the keyboard,
just type polly at
the operating system prompt: 

      Prompt> polly<ret>

      POLLY will then respond with a SMILES: prompt.  At this
point, type in the
SMILES string to specify the compound.  The indices, or an error
message if an
invalid SMILES string, will be output to the console.  A sequence
number is output as
well.  This number is just how many compounds POLLY has processed
during the
current session.
      The usage of POLLY in batch mode has the following format:

      Prompt> polly input_name <output_name> <error_name>

      Here input_name is the name of the file with molecule
identifiers and SMILES
strings (See Sec III for descriptions).  The default extension for
this file is ".smi" and
may be dropped from the command line.  If any other extension is
used it must be
explicitly stated.  By default, POLLY will write indices to a file
with the same base
name as the input file, appending the extension .mci and error
messages to a file with
the extension .err.  For example, if a user runs POLLY with the
following command
line:

   polly test.smi

indices will be written to test.mci and error messages will be
written to test.err.  You
my override these defaults by specifying the output and error file
names on the
command line.

III. Input

A. Format

      For batch mode, POLLY requires an identifier followed by one
or more spaces,
and a SMILES21 string (described below).  The sequence number and
SMILES string
must occur on one line.  The identifier may be composed of any
ASCII character,
excluding white space characters and is limited to 80 characters in
length.

B. SMILES string

      POLLY uses the SMILES (Simplified Molecular Identification
and Line Entry
System) method for specifying topological structure of a compound.
      The structure represented by a SMILES string should, under
most
circumstances, be hydrogen suppressed.  The SMILES interpreter
within POLLY will
determine the location of hydrogens implicitly by the normal
valence of the atoms to
which they would be connected.

1. Atom representation

      Each atom is represented by its atomic symbol.  For single
letter symbols, use
lower case letters to represent aromatic atoms, upper case letters
to represent
aliphatic atoms.  Double letter symbols are represented be an
uppercase first letter,
lowercase second letter.  If you must indicate aromaticity of an
atom with a double
letter symbol, the symbol should be followed by an "!".
      Double letter symbols can have ambiguous interpretation.  For
example, the
symbol for silicon, Si, could be interpreted as aliphatic sulfur
bonded to aromatic
iodine.  Any double letter symbol that could have ambiguous
interpretation should be
enclosed in square brackets "[]".  Silicon would then be
represented by [Si].  If the
double letter symbol would not have ambiguous interpretation, the
brackets are not
required (e.g. bromine is Br, not [Br]).

Examples:  Chlorine              Cl or [Cl]
           Silicon               [Si]
           Aliphatic carbon      C
           Aromatic carbon       c

2. Bonds

      By default, the bond between any two atoms is a single bond
(see section
III.B.4, aromatic rings for an exception).  To override this
default, the bond must be
explicitly represented.  The following bond types are available:

           Single     -
           Double     =
           Triple     #

Examples:  Ethane     CC or C-C
           Ethene     C=C
           Ethyne     C#C

3. Branches

      When an atom has more than two connecting atoms, the
additional connecting
chains should be enclosed in parentheses.  The chain within a set
of parentheses is
interpreted as being connected to the atom immediately preceding
the left parenthesis. 
You may nest parentheses.

Examples:  Carbon tetrachloride  ClC(Cl)(Cl)Cl
           Di-n-butylphosphate   O=P(OCCCC)OCCCC or
                                 CCCCOP(=O)OCCCC

      Note in the second SMILES string for Di-n-butylphosphate the
double bond to
the oxygen is also enclosed within the parentheses.  Any bonding
information to an
atom within parentheses must also be enclosed within the
parentheses.

4. Rings

      To represent a ring as a linear structure, one bond in the
ring must be broken. 
This structure can then be represented as a linear string.  To
identify where the
broken bond occurred, each atom that was involved is labeled with
a digit(s).  These
two atoms comprise a ring-closure pair.  The digit is placed
following the two atoms
that had the bond broken between them.  The interpreter may then
re-establish the
bond in the connection matrix.
      Two digits may be used to identify ring-closure pairs if they
are preceded by the
character "%".  Therefore, up to 99 (1-99) rings may be labeled.

Examples:  Cyclohexane           C1CCCCC1
           1-Methylcyclopentene  CC%11=CCCC%11

      Aromatic ring: SMILES notation allows atoms in aromatic rings
to be
represented with lower case atomic symbols.  This avoids having to
designate
conjugated double bonds in aromatic rings, i.e. the default is not
a single bond, but the
conjugated double bond.

Examples:  Benzene               c1ccccc1
           Naphthalene           c1cc2ccccc2cc1

5. Atom Qualifiers

      Placing square brackets around an atom symbol allows you to
specify additional
information about an atom that can not be implicitly deduced from
the connection
table.  This would include formal charges or hydrogens about an
aromatic nitrogen.

Examples:  Pyrrole               c1cccc[nH]1
           Tetramethylammonium   C[N+](C)(C)C

6. Restrictions

a. POLLY utilizes only a subset of all possible atoms, those that
allow the
representation of most organic compounds.
b. The maximum SMILES string length is 120.
c. The maximum number of atoms for any compound is 120.
d. Only compounds that can be represented by a connected graph are
allowed.
e. Hydrogens should not be included in the SMILES string except as
qualifiers.

IV. Output

      Appendix 1 describes the indices output by POLLY.  The order
the indices are
listed corresponds to the order in which they are output by POLLY. 
Appendix 2 lists
the parameters output on a record by record basis.

V.  References

1.    I. Gutman, B. Ruscic, N. Trinajstic and C. F. Wilcox, Jr.,
Graph theory and
      molecular orbitals, Part XII. Acyclic polyenes. J. Chem.
Phys., 62, 3339-3405
      (1975).

2.    H. Wiener, Structural determination of paraffin boiling
points, J. Amer. Chem.
      Soc., 69, 17-20 (1947).

3.    M. Randic', On characterization of molecular branching, J.
Am. Chem. Soc. 97,
      6609-6615 (1975).

4.    L.B. Kier and L.H. Hall, Molecular Connectivity in
Structure-Activity Analysis
      (Research Studies Press, Letchworth, Hertfordshire, U.K.,
1986).

5.    S.C. Basak, V.R. Magnuson, G.J. Niemi and R.R. Regal,
Determining structural
      similarity of chemicals using graph-theoretic indices,
Discrete Applied
      Mathematics, 19, 17 (1988); Special Volume: Applications of
Graph Theory in
      Chemistry and Physics, J.W. Kennedy and L.V. Quintas (eds.).

6.    D. Bonchev and N. Trinajstic, Information theory, distance
matrix and molecular
      branching, J. Chem. Phys., 67, 4517-4533 (1977).

7.    A.B. Roy, S.C. Basak, D.K. Harriss and V.R. Magnuson,
Neighborhood
      Complexities and Symmetry of Chemical graphs and their
biological
      applications, in Mathematical Modelling in Science and
Technology, X.J.R.
      Avula, R.E. Kalman, A.I. Lipais and E.Y. Rodin (Eds.), p.
745, Pergamon Press,
      1984.

8.    S.C. Basak, Use of molecular complexity indices in predictive
pharmacology
      and toxicology: a QSAR approach, Med. Sci. Res., 15, 605
(1987).

9.    C. Raychaudhury, S.K. Ray, J.J. Ghosh, A.B. Roy and S.C.
Basak,
      Discrimination of isomeric structures using
information-theoretic topological
      indices, J. Comput. Chem., 5, 581 (1984).

10.   N. Rashevsky, Life, information theory and topology, Bull.
Math. Biophys., 17,
      229-235 (1955).

11.   M. Randic', in: Computer Based Methods of Molecular
Similarity, ed. G.M.
      Maggiora (John Wiley, in press, 1989).

12.   S.C. Basak, V.R. Magnuson, G.J. Niemi, R.R. Regal and G.D.
Veith,
      Topological indices: their nature, mutual relatedness, and
applications,
      Mathematical Modelling, 8, 300 (1987).

13.   M. Johnson, S.C. Basak and G. Maggiora, A characterization of
molecular
      similarity methods for property prediction, Mathematical and
Computer
      Modelling, II, 630 (1988).

14.   M. Lajiness, Molecular Similarity Based Methods for Selecting
compounds for
      Screening, in: Computational Chemical Graph Theory, Ed. D. H.
Rouvray,
      Nova, New York. pp. 299-316 (199).

15.   S.C. Basak, S. Bertelsen and G.D. Grunwald, Application of
graph theoretic
      parameters in quantifying molecular similarity and
structure-activity
      relationships, presented at the Fifth International
Conference on Mathematical
      Chemistry (1993).

16.   S.C. Basak and G.D. Grunwald, Use of graph invariants, volume
and total
      surface area in predicting boiling point of alkanes,
Mathematical Modelling and
      Scientific Computing, 2, 735-740 (1993).

17.   S.C. Basak, G.J. Niemi and G.D. Veith, Optimal
characterization of structure for
      prediction of properties, J. Math. Chem., 4, 185 (1990).

18.   Basak, S.C.  A Nonempirical Approach to Predicting Molecular
Properties using
      Graph-Theoretic Invariants, in PRACTICAL APPLICATIONS OF
      QUANTITATIVE STRUCTURE-ACTIVITY RELATIONSHIPS (QSAR) IN
      ENVIRONMENTAL CHEMISTRY AND TOXICOLOGY, eds. W. Karcher and
J.
      Devillers, Kluwer Academic Publishers, (1990).

19.   G.J. Niemi, S.C. Basak, G.D. Veith and G. Grunwald,
Prediction of octanol-
      water partition coefficient (Kow) using
algorithmically-derived variables,
      Environmental Toxicology and Chemistry, 11, 893-900 (1992).

20.   G.J. Niemi, S.C. Basak and G.D. Veith, A theoretical and
computational
      approach to chemical evaluation based on structure-activity
relationships,
      Procedeedings of the First Conference of the International
Society of
      Environmental Protection, pp 57-68 (1990).

21.   E.B. Anderson, G.D. Veith, and D. Weininger, SMILES: A Line
notation and
      computerized interpreter for chemical structures,
Environmental Research Brief,
      U.S. EPA, (1987).

!
Appendix 1:  The 98 topological indices calculated by POLLY.

IWD        Information index for the magnitudes of distances
between all possible
           pairs of vertices of a graph

IWD        Mean information index for the magnitude of distance

W          Wiener index = half-sum of the off-diagonal elements of
the distance
           matrix of a graph

ID         Degree complexity

HV         Graph vertex complexity

HD         Graph distance complexity

IC         Information content of the distance matrix partitioned
by frequency of
           occurrences of distance h

O          Order of neighborhood when ICr reaches its maximum value
for the
           hydrogen-filled graph

IORB       Information content or complexity of the
hydrogen-suppressed graph at
           its maximum neighborhood of vertices

OORB       Maximum order of neighborhood of vertices for IORB
within the hydrogen-
           suppressed graph

M1         A Zagreb group parameter = sum of square of degree over
all vertices

M2         A Zagreb group parameter = sum of cross-product of
degrees over all
           neighboring (connected) vertices

ICr        Mean information content or complexity of a graph based
on the rth (r =
           0..6) order neighborhood of vertices in a
hydrogen-filled graph

SICr       Structural information content for rth (r = 0..6) order
neighborhood of
           vertices in a hydrogen-filled graph

CICr       Complementary information content for rth (r = 0..6)
order neighborhood
           of vertices in a hydrogen-filled graph

h!         Path connectivity index of order h = 0..6

h!C        Cluster connectivity index of order h = 3..6

h!Ch       Chain connectivity index of order h = 3..6

h!PC       Path-cluster connectivity index of order h = 4..6

h!b        Bonding path connectivity index of order h = 0..6

h!bC       Bonding cluster connectivity index of order h = 3..6

h!bCh      Bonding chain connectivity index of order h = 3..6

h!bPC      Bonding path-cluster connectivity index of order h =
4..6

h!v        Valence path connectivity index of order h = 0..6

h!vC       Valence cluster connectivity index of order h = 3..6

h!vCh      Valence chain connectivity index of order h = 3..6

h!vPC      Valence path-cluster connectivity index of order h =
4..6

Ph         Number of paths of length h = 0..10
!
Appendix 2: Format of the POLLY output file

Record  1: Chemical id
                 (a80)

Record  2: IWD, IWD, W, ID, HV, HD, IC
                 (f11.3, f8.3, i6, 4f8.3)

Record  3: O, IORB, OORB, M1, M2
                 (i6, f8.3, 3i6)

Record  4: IC0, IC1, ..., IC6
                 (7f8.3)

Record  5: SIC0, SIC1, ..., SIC6
                 (7f8.3)

Record  6: CIC0, CIC2, ..., CIC6
                 (7f8.3)

Record  7: 0!, 1!, ..., 6!
                 (7f8.3)

Record  8: 3!C, 4!C, 5!C, 6!C
                 (24x, 4f8.3)

Record  9: 3!Ch, 4!Ch, 5!Ch, 6!Ch
                 (24x, 4f8.3)

Record 10: 4!PC, 5!PC, 6!PC
                 (32x, 3f8.3)

Record 11: 0!b, 1!b, ..., 6!b
                 (7f8.3)

Record 12: 3!bC, 4!bC, 5!bC, 6!bC
                 (24x, 4f8.3)

Record 13: 3!bCh, 4!bCh, 5!bCh, 6!bCh
                 (24x, 4f8.3)

Record 14: 4!bPC, 5!bPC, 6!bPC
                 (32x, 3f8.3)

Record 15: 0!v, 1!v, ..., 6!v
                 (7f8.3)

Record 16: 3!vC, 4!vC, 5!vC, 6!vC
                 (24x, 4f8.3)

Record 17: 3!vCh, 4!vCh, 5!vCh, 6!vCh
                 (24x, 4f8.3)

Record 18: 4!vPC, 5!vPC, 6!vPC
                 (32x, 3f8.3)

Record 19: P0, P1, ..., P10
                 (11i6)

------------------------------------------------------------------------

From: [email-masked] (Leif Norskov)

Molconn-X is *THE* program for calculating topological indices.
( - sometimes referred to as Kier and Hall indices).
It is available for $ 295 for academic users from
	Lowell H. Hall
	Hall Associates Consulting
	2 Davis Street
	Quincy, MA 02170, U.S.A.
	Tel. (617) 773-4833
Lowell does not seem to have an email address, but he certainly
does put some nice stamps on his ordinary mail :-)

------------------------------------------------------------------------

From: "Igor Baskin" <[email-masked]>

In connection with your inquiry about topological indexes, I
enclose a small extraction from the description of the
EMMA package.

"EMMA" ("EFFECTIVE MODELLING OF MOLECULAR ACTIVITY") - THE SOFTWARE
     FOR THE PREDICTION OF PROPERTIES/BIOLOGICAL ACTIVITIES OF
       ORGANIC COMPOUNDS ON THE BASIS OF REGRESSION ANALYSIS
...
     For each  structure  in  a  training set EMMA allows to
compute from hundreds to thousands of descriptors.  The  set
of descriptors   includes   topological   indices   (various
connectivity indices,  Balaban index J,  Wiener and extended
Wiener, Hosoya,  Merrifield-Simmons,  Gutman  and some other
indices), informational indices,  the indices which are  the
functions of  charge distribution in molecules,  the indices
based on  atomic  electronegativities  and  those  based  on
inductive parameters,  steric indices, various local indices
and, what is important,  the substructural descriptors which
are equal  to  the  number of chaines (1- to 9-atomic),  the
number of cycles  (3-  to  6-membered)  and  the  number  of
branched fragments  (4-,  5-,  and  6-atomic),  the atoms in
substructures being  classified  taking  into  account   the
number of  hydrogens at them,  bond types and formal charge.
EMMA can manage 2000 descriptors computed and construct  the
regression equations    including    only   a   few   "best"
descriptors. A  user  can  easily  add  his  own  descriptor
programs or  can  input  the  additional  descriptor  values
manually.

...

     Developers:
     Professor N.S.Zefirov,  Department of Chemistry, Moscow State
     University, Moscow, 119899, Russia. Fax: (095) 939-0290,
     phone (095) 939-1620
     Dr. D.V.Sukhachev, Dr. I.I.Baskin, Dr. V.A.Palyulin