Protein alignment: Exact versus approximate. An illustration.

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.

On the centrality of vertices of molecular graphs.

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.

Common vertex matrix: a novel characterization of molecular graphs by counting.

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.

Very efficient search for nucleotide alignments.

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.

Conjugated circuits currents in hexabenzocoronene and its derivatives formed by joining proximal carbons.

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.

Applying the conjugated circuits method to Clar structures of [n]phenylenes for determining resonance energies.

We consider the aromaticity of biphenylene and structurally related linear or angular [n]phenylenes for which the direct application of the model of conjugated circuits does not offer valid expressions for resonance energy and aromaticity. We located the cause of this problem as being due to Kekulé valence structures in which neighboring benzenoid rings are connected by two CC double bonds. By restricting the selection of Kekulé valence structures to those that contribute to Clar structures of such systems, we were able to show that linear and angular [n]phenylenes have approximately similar resonance energies, with angular [n]phenylenes being slightly more stable due to second order contributions arising from disjoint conjugated circuits. Expressions for resonance energies of [n]phenylenes up to n = 8 are listed and recursion expressions for higher n values are outlined.

Algebraic clar formulas - numerical representation of clar structural formula.

We outline the construction of an algebraic (numerical) representation for Clar's valence formulas which in their geometrical form are illustrated with π-aromatic sextets as inscribed circles in benzenoid rings.

Study of proteome maps using partial ordering.

This paper describes numerical characterization of proteome maps based on partial ordering of protein spots with respect to the mass and the charge. The partial ordering diagram is embedded directly over the 2D map and the corresponding adjacency matrix is constructed. The adjacency matrix is augmented by including the information on the abundance of proteins in a gel as suitably scaled diagonal entries of the matrix. The approach is illustrated on proteome maps of Anderson et al. (1996) based on experimental results from liver cells of rats exposed to four peroxisome proliferators. We used the leading eigenvectors of the adjacency matrices as maps descriptors in order to determine the degree of similarity between proteome maps.

Novel graph distance matrix.

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.

Graphical representation of proteins as four-color maps and their numerical characterization.

We put forward a novel compact 2-D graphical representation of proteins based on the concept of virtual genetic code and a four-color map. The novel graphical representation uniquely represents proteins and allows one to easily and quickly visually observe and inspect similarity/dissimilarity between them. It also leads to a novel protein descriptor, a 10-dimensional vector derived from a novel structure matrix S associated with the map. The introduced numerical characterization of proteins is not only useful for their comparative study, but also for cataloguing information on a single protein. The approach is illustrated with the A chain of human insulin and the A chain of human insulin analogue glargine.

A new yardstick for benzenoid polycyclic aromatic hydrocarbons.

The newly introduced signature of benzenoids (a sequence of six real numbers Si with i = 6-1) shows the composition of the pi-electron partition by indicating the number of times all rings of the benzenoid are assigned 6, 5, 4, 3, 2, or 1 pi-electrons. It allows the introduction of a new ordering criterion for such polycyclic aromatic hydrocarbons by summing some of the terms in the signature. There is an almost perfect linear correlation between sums S6 + S5 and S4 + S3 for isomeric cata- or peri-fused benzenoids, so that one can sort such isomers according to ascending s 6 + S5 or to descending S4 + S3 sums (the resulting ordering does not differ much and agrees with that based on increasing numbers of Clar sextets and of Kekule structures). Branched cata-condensed benzenoids have higher S6 + S5 sums than isomeric nonbranched systems. For nonisomeric peri-condensed benzenoids, both sums increase with increasing numbers of benzenoid rings and decrease with the number of internal carbon atoms. Other partial sums that have been explored are S6 + S5 + S3 And S6 + S2 + S1, and the last one appears to be more generally applicable as a parameter for the complexity of benzenoids and for ordering isomeric benzenoids.

Pi-electron partitions, signatures, and Clar structures of selected benzenoid hydrocarbons.

It is shown for a representative set of isomeric benzenoids that pi-electron partitions and signatures can serve for characterizing and ordering benzenoids. Benzenoid signatures (sequences s6 through s1 where the subscripts correspond to numbers of pi electrons in all rings) are obtained by examining the numbers of assigned pi electrons ranging from 6 to 1 for each ring in all resonance structures. The pi-electron partitions and signatures of all 33 non-isoarithmic peri-condensed benzenoid hydrocarbons with eight rings and four contiguous internal carbon atoms allow an ordering of these benzenoids that agrees fairly well with increasing numbers of Kekulé valence structures and Clar sextets. Interestingly, an excellent correlation (R2 > 0.99) is observed between s6 + s5 + s2 + s1 and s4 + s3, and an explanation for this observation is provided: the number P of pi electrons is divided unequally between two components: s34 = s4 + s3 and s1256 = s6 + s5 + s2 + s1 so that s1256 or the quotient s1256/s34 = Q can serve as a new metric for perfect matchings of polyhexes and a criterion for ordering and for evaluating the complexity of isomeric benzenoids quantitatively.

Numerical Kekulé structures of fullerenes and partitioning of pi-electrons to pentagonal and hexagonal rings.

We calculated the partitioning of pi-electrons within individual pentagonal and hexagonal rings of fullerenes for a collection of fullerenes from C20 to C72 by constructing their Kekulé valence structures and averaging the pi-electron content of individual rings over all Kekulé valence structures. The resulting information is collected in Table 2, which when combined with the Schlegel diagram of fullerenes (illustrated in Figure 7) uniquely characterizes each of the 19 fullerenes considered. The results are interpreted as the basic information on the distributions (variation) of the local (ring) pi-electron density.

On representation of proteins by star-like graphs.

To arrive at graphical representations of proteins one is confronted with number of arbitrary decisions how to assign the 20 natural amino acids to equivalent or non-equivalent sites of underlying geometrical objects used for construction of their graphical representation. Here we consider representation of proteins based on generalized star graphs, which are graphs with one vertex of maximal degree in the center to which are attached other vertices of either degree one or two. The matrix representation of proteins based on star-like graphs has an important advantage in that, while its pictorial representation depends on selected assignment of amino acids to various branches of star graph, its properties do not depend on the adopted assignment of vertices to amino acids. Hence, the derived graph invariants, devoid of artifacts associated with graphical representations of biosequences, will better reflect upon the inherent properties of protein structure. We describe several graph invariants, mostly extracted from distance matrices of star-like graphs, which can serve as protein descriptors. The approach is illustrated on strand A of the human insulin.

Characterization of complex biological systems by matrix invariants.

One direction in exploring similarities among biological sequences (such as DNA, RNA, and proteins), is to associate with such systems ordered sets of sequence invariants. These invariants represent selected properties of mathematical objects, such as matrices, that one can associate with biological sequences. In this article, we are exploring properties of recently introduced Line Distance matrices, and in particular we consider properties of their eigenvalues. We prove that Line Distance matrices of size n have one positive and n - 1 negative eigenvalues. Visual representation of Cauchy's interlacing property for Line Distance matrices is considered. Matlab programs for line distance matrices and examples are available on the following website: www.fmf.uni-lj.si/ approximately jaklicg/ldmatrix.html.

Quantitative characterizations of proteome: dependence on the number of proteins considered.

We consider the sensitivity of numerical characterizations of proteome on the number of proteins considered in the analysis. We examined data on proteomics maps belonging to the liver cells of mice subject to four proliferators. We varied the number of proteins considered for quantitative analysis from 25 up to 1000 proteins. For each case, we have compared the similarity/dissimilarity results when different number of proteins has been considered. We found that proteins maps based on a set of about 300 most abundant proteins spots suffice for satisfactory numerical characterization of corresponding proteome.

"Anticonnectivity": a challenge for structure-property-activity studies.

The higher-order variable connectivity indices were introduced to account for the combination of positive and negative relative contributions of atoms and bonds in the construction of the quantitative structure-property relationships or quantitative structure-activity relationships models. The coding capabilities of modified descriptors were presented on the modeling of the atmospheric reaction rate constants of selected organic compounds with OH radicals. The optimization of diagonal weights of the augmented adjacency matrix pointed out the significant enhancing effect of oxygen and the suppressive effect of chlorine on the overall molecular atmospheric reactivity of organic compounds with OH radicals. The linear regression model, using a single structural descriptor, that is, a variable connectivity index of order one, produced a root-mean-square error of 0.343 log units. Although the obtained calculation error was higher than in previously reported multiple linear regression models, the new model offered important insight into the role of the individual structural components that are influencing the reactivity of organic compounds.

Partitioning of pi-electrons in rings for Clar structures of benzenoid hydrocarbons.

Resonance structures of polycyclic aromatic hydrocarbons can be associated with numerical formulas by assigning pi-electrons of C=C double bonds to individual benzenoid rings. Each C=C double bond in a resonance structure assigns two pi-electrons to a ring in a fused-benzenoid system if it is not shared by adjacent rings and one pi-electron when it is common to two rings, obtaining thus a "local" characterization of rings in polycyclic conjugated hydrocarbons. In the present contribution we extend this approach to the aromatic pi-sextet model of Clar, which offers an alternative description of benzenoid hydrocarbons. In this model local characteristics of individual benzenoid rings are based on partitioning of pi-electrons but only for those resonance structures (fewer in number) that contribute to Clar's formula of benzenoid hydrocarbons.

On the dependence of a characterization of proteomics maps on the number of protein spots considered.

We have reexamined the numerical characterization of proteomics maps based on the construction of novel distance matrices associated with the nearest neighbor graph for the protein spots. In particular we consider dependence of a characterization of proteomics map on the number of proteins considered in the analysis. We examined a collection of proteomics maps in which we approximately doubled the number of spots to be used for quantitative analysis, considering cases of maps having 30, 50, 100, 250, 500, and 1054 protein spots. For each case we have compared the similarity-dissimilarity results for five proteomics maps of rat liver cells associated with the control group and four proliferators administrated by intraperitoneal injection. We found that proteins maps based on a set of about the 250 most abundant proteins spots suffice for a satisfactory numerical characterization of such maps.