Research On The Inverse Wiener Index Problem In Combinatorial Chemistry

Combinatorial chemistry is a powerful new technology in drug design and molecular recognition. It is a wet-laboratory methodology aimed at "massively parallel" screening of chemical compounds for the discovery of compounds that have a certain biological activity. The power of the method comes from the interaction between experimental design and computational modeling.Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents an atom of molecule, and covalent bonds between atoms are represented by edges between the corresponding vertices. This polygonal shape derived from a chemical compounds is often called its molecular graph, and can be a path, a tree, or in general a graph. An indicator defined over this molecular graph, the Wiener index, has been shown to be strongly correlated to various chemical properties of the compounds. Intensive work has been done on the theory of Wiener indices. There are broadly two types of problems that all of the previous work has addressed—Wiener index problem for graphs and the inverse Wiener index problem.The inverse Wiener problem seeks to answer , give an integer n, the question about the existence of a tree T such that W(T)=n, and when this is the case, how to compute it efficiently. The Wiener index conjecture for trees states that for any integer n (except for a finite set), one can find a tree with Wiener index n. This conjecture has been open for quite some time, and many authors have presented incremental progress on this problem. In 2000, Goldman et al attempt to solve the problem by defining a recurrence relation on Wiener indices of trees by using dynamic programming to construct trees from smaller sub trees. Although the dynamic programming algorithm proposed by Goldman et al can solve this problem, its performance is still not very satisfying. Not only is the algorithm very computationally expensive, but the complexity and speed of it are also very demanding.In this paper, we mainly studied the relation between Wiener index and some other topological indices, by virtue of which we made many improvements to this algorithm. Then we present further progress towards proving this conjecture—through the design of efficient algorithm, we show that enumerating all possible trees to verify this conjecture (as done by all the previous approaches) is not necessary, but instead searching in a small special family of trees suffices. More precisely, the main contributions are:1) We refined the algorithm for the inverse Wiener index problem of trees proposed by Goldman et al in 2000. By comparison we show that the new algorithm was better than the original algorithm in the amount of recursions and the search space.2) We presented an infinite family of trees and prove various properties of these trees to show that it is a good candidate to analyze, rather than searching over the exponential space of all possible trees.3) We presented several efficient algorithms for the inverse Wiener index problem, using variants of the Frederickson and Johnsons matrix searching algorithm. Through the algorithms we can show that a lager number of integers, up to at least 10~8, are representable as Wiener indices of trees in this succinct family, compared with the previous best 10~4.