the starting molecule from which the distance distribution was obtained. This
subsection tries to tackle this drawback by slightly relaxing the distance distribution
matching criteria for the trees with number of vertices deviating from the source or
starting distribution. This deviation can either lead to increased or decreased
number of vertices.
(a) Non-Isomorphic Canonical Tree Generation with Relaxed Distance
Distribution
The first step involves specifying the number of vertices (after factoring in the
deviation) and then generating the trees. Positive deviation means required number
of vertices is greater than that in the current tree while negative deviation means the
required number of vertices is lesser. However, since exact distance distribution
matching is not possible in this case, two variants of relaxed distribution matching
are considered as explained below:
Strong matching—This situation arises when the distance distribution of the
generated tree can be obtained from the starting/source distance distribution by
either adding or deleting vertices at any level (named node deviation) although
simultaneous insertion or deletion of vertices is not allowed for a given deviation. In
essence, the obtained distance distribution corresponds to a pruned tree of the
source distance distribution if the node deviation is negative and vice versa if the
node deviation is positive.
Thus, to put it mathematically, if trees are to be generated by decreasing or
increasing n number of vertices, then only n deletions or insertions are allowed so
that:
X e
i¼1
c
s
i À c
p
i
À
Á
¼ n
where c
s
i is the count of vertices at level i in the source distance distribution; c
p
i is
the count of vertices at level i in the present distance distribution under consideration; and e is the maximum of the eccentricity of the source and present distance
distribution.
Weak matching—In this case, the distance distribution matching criteria is further relaxed in that one can add and delete vertices simultaneously at any level.
This, in effect, executes migration of vertices from one level to another (named
node migration). If this is allowed without a cap on the number of node migrations,
then all the possible structure generation will be considered a match which will
include the linear chain too. Presumably, in order to match the source distance
distribution closely using weak matching criterion, number of allowed node
migrations should be provided preferably of low value.
For this exercise, if the trees are to be obtained by decreasing or increasing
n number of vertices, then n deletions or insertions along with m migrations are
allowed that satisfies the following criteria:
88
Md.I. H. Rizvi et al.
subsection tries to tackle this drawback by slightly relaxing the distance distribution
matching criteria for the trees with number of vertices deviating from the source or
starting distribution. This deviation can either lead to increased or decreased
number of vertices.
(a) Non-Isomorphic Canonical Tree Generation with Relaxed Distance
Distribution
The first step involves specifying the number of vertices (after factoring in the
deviation) and then generating the trees. Positive deviation means required number
of vertices is greater than that in the current tree while negative deviation means the
required number of vertices is lesser. However, since exact distance distribution
matching is not possible in this case, two variants of relaxed distribution matching
are considered as explained below:
Strong matching—This situation arises when the distance distribution of the
generated tree can be obtained from the starting/source distance distribution by
either adding or deleting vertices at any level (named node deviation) although
simultaneous insertion or deletion of vertices is not allowed for a given deviation. In
essence, the obtained distance distribution corresponds to a pruned tree of the
source distance distribution if the node deviation is negative and vice versa if the
node deviation is positive.
Thus, to put it mathematically, if trees are to be generated by decreasing or
increasing n number of vertices, then only n deletions or insertions are allowed so
that:
X e
i¼1
c
s
i À c
p
i
À
Á
¼ n
where c
s
i is the count of vertices at level i in the source distance distribution; c
p
i is
the count of vertices at level i in the present distance distribution under consideration; and e is the maximum of the eccentricity of the source and present distance
distribution.
Weak matching—In this case, the distance distribution matching criteria is further relaxed in that one can add and delete vertices simultaneously at any level.
This, in effect, executes migration of vertices from one level to another (named
node migration). If this is allowed without a cap on the number of node migrations,
then all the possible structure generation will be considered a match which will
include the linear chain too. Presumably, in order to match the source distance
distribution closely using weak matching criterion, number of allowed node
migrations should be provided preferably of low value.
For this exercise, if the trees are to be obtained by decreasing or increasing
n number of vertices, then n deletions or insertions along with m migrations are
allowed that satisfies the following criteria:
88
Md.I. H. Rizvi et al.