Search

We illustrate solving the protein alignment problem exactly using the algorithm VESPA (very efficient search for protein alignment). We have compared our result with the approximate solution obtained with BLAST (basic local alignment search tool) software, which is currently the most widely used for searching for protein alignment. We have selected human and mouse proteins having around 170 amino acids for comparison. The exact solution has found 78 pairs of amino acids, to which one should add 17 individual amino acid alignments giving a total of 95 aligned amino acids. BLAST has identified 64 aligned amino acids which involve pairs of more than two adjacent amino acids. However, the difference between the two outputs is not as large as it may appear, because a number of amino acids that are adjacent have been reported by BLAST as single amino acids. So if one counts all amino acids, whether isolated (single) or in a group of two and more amino acids, then the count for BLAST is 89 and for VESPA is 95, a difference of only six., (© 2015 Wiley Periodicals, Inc.)

For acyclic systems the center of a graph has been known to be either a single vertex of two adjacent vertices, that is, an edge. It has not been quite clear how to extend the concept of graph center to polycyclic systems. Several approaches to the graph center of molecular graphs of polycyclic graphs have been proposed in the literature. In most cases alternative approaches, however, while being apparently equally plausible, gave the same results for many molecules, but occasionally they differ in their characterization of molecular center. In order to reduce the number of vertices that would qualify as forming the center of the graph, a hierarchy of rules have been considered in the search for graph centers. We reconsidered the problem of "the center of a graph" by using a novel concept of graph theory, the vertex "weights," defined by counting the number of pairs of vertices at the same distance from the vertex considered. This approach gives often the same results for graph centers of acyclic graphs as the standard definition of graph center based on vertex eccentricities. However, in some cases when two nonequivalent vertices have been found as graph center, the novel approach can discriminate between the two. The same approach applies to cyclic graphs without additional rules to locate the vertex or vertices forming the center of polycyclic graphs, vertices referred to as central vertices of a graph. In addition, the novel vertex "weights," in the case of acyclic, cyclic, and polycyclic graphs can be interpreted as vertex centralities, a measure for how close or distant vertices are from the center or central vertices of the graph. Besides illustrating the centralities of a number of smaller polycyclic graphs, we also report on several acyclic graphs showing the same centrality values of their vertices., (Copyright © 2013 Wiley Periodicals, Inc.)

We present a novel matrix representation of graphs based on the count of equal-distance common vertices to each pair of vertices in a graph. The element (i, j) of this matrix is defined as the number of vertices at the same distance from vertices (i, j). As illustrated on smaller alkanes, these novel matrices are very sensitive to molecular branching and the distribution of vertices in a graph. In particular, we show that ordered row sums of these novel matrices can facilitate solving graph isomorphism for acyclic graphs. This has been illustrated on all undecane isomers C11H24 having the same path counts (total of 25 molecules), on pair of graphs on 18 vertices having the same distance degree sequences (Slater's graphs), as well as two graphs on 21 vertices having identical several topological indices derived from information on distances between vertices., (Copyright © 2013 Wiley Periodicals, Inc.)

We describe a very efficient search for nucleotide alignments, which is analogous to the novel very efficient search for protein alignment. Just as it has been the case with the alignment of proteins, based on 20 × 20 adjacency matrices for amino acids, obtained from a superposition of labeled amino acids adjacency matrices for the proteins considered, one can construct labeled matrices of size 4 × 4, listing adjacencies of nucleotides in DNA sequence. The matrix elements correspond to 16 pairs of adjacent nucleotides. To obtain DNA alignments, one combines information in the corresponding matrices for a pair of DNA nucleotides. Matrices are obtained by insertion of the sequential labels for pairs of nucleotides in the corresponding cells of the 4 × 4 tables. When two such matrices are superimposed, one can identify all segments in two DNA sequences, which are shifted relative to one another by the same amount in either direction, without using trial-and-error displacements of the two sequences one relative to the other to find local nucleotide alignments., (Copyright © 2012 Wiley Periodicals, Inc.)

We report on calculated CC bond currents for a dozen derivatives of hexabenzocoroenene in which one or more proximal carbon atoms at the molecular periphery have been bridged. The approach that we use is graph-theoretical in nature, following our outline of this method in 2003, which is based on finding all conjugated circuits in all Kekulé valence structures of these molecules. To the π-electrons having 4n + 2 π-electrons are assigned anticlockwise π-electron currents and to conjugated circuits having 4n π-electrons are assigned π-electron currents. One may summarize the results reported in this work by stating that CC bond currents in the compounds considered decrease on going from peripheral rings to the central ring of the molecule, and also that CC bond currents decrease by insertion of bridges to proximal peripheral benzenoid rings., (Copyright © 2012 Wiley Periodicals, Inc.)

A novel approach to the problem of protein alignments is described, which in comparison with existing approaches is visibly more efficient. This approach is based on superposition of amino acid adjacency matrices of a pair of proteins, which have been modified to record the sequential order of amino acids. As a result, one obtains simultaneously all segments of the two proteins which are shifted relative to one another by one or more positions in either directions, without need of a prior exhaustive search for an alignment that included unproductive directions and unknown displacement steps., (Copyright © 2011 Wiley Periodicals, Inc.)

We have introduced novel distance matrix for graphs, which is based on interpretation of columns of the adjacency matrix of a graph as a set of points in n-dimensional space, n being the number of vertices in the graph. Numerical values for the distances are based on the Euclidean distance between n points in n-dimensional space. In this way, we have combined the traditional representation of graphs (drawn as 2D object of no fixed geometry) with their representation in n-dimensional space, defined by a set of n-points that lead to a representation of definite geometry. The novel distance matrix, referred to as natural distance matrix, shows some structural properties and offers novel graph invariants as molecular descriptors for structure-property-activity studies. One of the novel graph descriptors is the modified connectivity index in which the bond contribution for (m, n) bond-type is given by 1/ radical(m + n), where m and n are the valence of the end vertices of the bond. The novel distance matrix (ND) can be reduced to sparse distance-adjacency matrix (DA), which can be viewed as specially weighted adjacency matrix of a graph. The quotient of the leading eigenvalues of novel distance-adjacency matrix and novel distance matrix, as illustrated on a collection of graphs of chemical interest, show parallelism with a simple measure of graph density, based on the quotient of the number of edges in a graph and the maximal possible number of edges for graphs of the same size., (Copyright 2010 Wiley Periodicals, Inc.)

String comparison techniques were developed and applied for measuring the molecular similarity of chemical structures. The molecular structures were encoded as a sequence of numbers representing counts of paths of different lengths. The similarity index between two compounds was calculated as the difference between the gains of information derived through comparison of the corresponding molecular path sequences. Ranks between the structures of the studied data base obtained according to this similarity were used as basic data for deriving correspondences between the elements of the set of compounds. The method was applied on a group of 41 barbiturates. Correlation equations were calculated for different groups of compounds grouped according to the displayed similarity. The correlation equations and the corresponding statistics were obtained using standard computer programs. Special algorithm for computing the similarity index and the correlation matrix (outlined very briefly) was developed and implemented on VAX 11/750., (Copyright © 1986 John Wiley & Sons, Inc.)