Search

Background: Post-translational modification (PTM) is a biological process that is associated with the modification of proteome, which results in the alteration of normal cell biology and pathogenesis. There have been numerous PTM reports in recent years, out of which, lysine phosphoglycerylation has emerged as one of the recent developments. The traditional methods of identifying phosphoglycerylated residues, which are experimental procedures such as mass spectrometry, have shown to be time-consuming and cost-inefficient, despite the abundance of proteins being sequenced in this post-genomic era. Due to these drawbacks, computational techniques are being sought to establish an effective identification system of phosphoglycerylated lysine residues. The development of a predictor for phosphoglycerylation prediction is not a first, but it is necessary as the latest predictor falls short in adequately detecting phosphoglycerylated and non-phosphoglycerylated lysine residues. Results: In this work, we introduce a new predictor named RAM-PGK, which uses sequence-based information relating to amino acid residues to predict phosphoglycerylated and non-phosphoglycerylated sites. A benchmark dataset was employed for this purpose, which contained experimentally identified phosphoglycerylated and non-phosphoglycerylated lysine residues. From the dataset, we extracted the residue adjacency matrix pertaining to each lysine residue in the protein sequences and converted them into feature vectors, which is used to build the phosphoglycerylation predictor. Conclusion: RAM-PGK, which is based on sequential features and support vector machine classifiers, has shown a noteworthy improvement in terms of performance in comparison to some of the recent prediction methods. The performance metrics of the RAM-PGK predictor are: 0.5741 sensitivity, 0.6436 specificity, 0.0531 precision, 0.6414 accuracy, and 0.0824 Mathews correlation coefficient.

Free radicals that form from reactive species of nitrogen and oxygen can react dangerously with cellular components and are involved with the pathogenesis of diabetes, cancer, Parkinson's, and heart disease. Cysteine amino acids, due to their reactive nature, are prone to oxidation by these free radicals. Determining which cysteines oxidize within proteins is crucial to our understanding of these chronic diseases. Wet lab techniques, like differential alkylation, to determine which cysteines oxidize are often expensive and time-consuming. We utilize machine learning as a fast and inexpensive approach to identifying cysteines with oxidative capabilities. We created the original features RAMmod and RAMseq for use in classification. We also incorporated well-known features such as PROPKA, SASA, PSS, and PSSM. Our algorithm requires only the protein sequence to operate; however, we do use template matching by MODELLER to acquire 3D coordinates for additional feature extraction. There was a mean improvement of RAM over N6C by 22.04% MCC. It was statistically significant with a p-value of 0.015. RAM provided a significant increase over PSSM with a p-value of 0.040 and an average 70.09% improvement MCC., Graphical Abstract Unlabelled Image

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved.

We study the Wasserstein metric to measure distances between molecules represented by the atom index dependent adjacency 'Coulomb' matrix, used in kernel ridge regression based supervised learning. Resulting machine learning models of quantum properties, a.k.a. quantum machine learning models exhibit improved training efficiency and result in smoother predictions of energies related to molecular distortions. We first illustrate smoothness for the continuous extraction of an atom from some organic molecule. Learning curves, quantifying the decay of the atomization energy's prediction error as a function of training set size, have been obtained for tens of thousands of organic molecules drawn from the QM9 data set. In comparison to conventionally used metrics (L1 and L2 norm), our numerical results indicate systematic improvement in terms of learning curve off-set for random as well as sorted (by norms of row) atom indexing in Coulomb matrices. Our findings suggest that this metric corresponds to a favorable similarity measure which introduces index-invariance in any kernel based model relying on adjacency matrix representations.

The extended adjacency matrix Ae(G) of a graph G is determined by graph degrees. Some inequalities are found for the extended adjacency matrix including its vertices, its edges and its degrees in this paper. Also, some bounds are established for this matrix involving its energy and its Laplacian energy.

The maximum eigenvalue of the adjacency matrix (AM) has been supposed to contain rich information about the corresponding network. An experimental study focused on revealing the meaning and application of the maximum eigenvalue is missing. To this end, AM was constructed using mutual information (MI) to determine the functional connectivity with electroencephalogram (EEG) data recorded with a mental fatigue model, and then was converted into both binary and weighted brain functional network (BFN) and corresponding random networks (RNs). Both maximum eigenvalue and corresponding network characters in BFNs and RNs were considered to explore the changes during the formation of mental fatigue. The results indicated that large maximum eigenvalue means more edges in the corresponding network, along with a high degree and a short characteristic path length both in weighted and binary BFNs. Interestingly, the maximum eigenvalue of AM was always a little larger than that of the corresponding random matrix (RM), and had an obvious linearity with the sum of the AM elements, indicating that the maximum eigenvalue can be able to distinguish the network structures which have the same mean degree. What is more, the maximum eigenvalue, which increased with the deepening of mental fatigue, can become a good indicator for mental fatigue estimation.

Fast and accurate ellipse detection is critical in certain computer vision tasks. In this paper, we propose an arc adjacency matrix-based ellipse detection (AAMED) method to fulfill this requirement. At first, after segmenting the edges into elliptic arcs, the digraph-based arc adjacency matrix (AAM) is constructed to describe their triple sequential adjacency states. Curvature and region constraints are employed to make the AAM sparse. Secondly, through bidirectionally searching the AAM, we can get all arc combinations which are probably true ellipse candidates. The cumulative-factor (CF) based cumulative matrices (CM) are worked out simultaneously. CF is irrelative to the image context and can be pre-calculated. CM is related to the arcs or arc combinations and can be calculated by the addition or subtraction of CF. Then the ellipses are efficiently fitted from these candidates through twice eigendecomposition of CM using Jacobi method. Finally, a comprehensive validation score is proposed to eliminate false ellipses effectively. The score is mainly influenced by the constraints about adaptive shape, tangent similarity, distribution compensation. Experiments show that our method outperforms the 12 state-of-the-art methods on 9 datasets as a whole, with reference to recall, precision, F-measure, and time-consumption.

An adjacency matrix A(G) of directed graph G is an m×m matrix consisting of only entries 0 and 1, where m is the number of vertices of G. The entry aij is equal to 1 if there exists a directed edge from vertex vi to vertex vj, otherwise it is equal to 0. Let D(G) be a diagonal matrix of size m×m with each of its main diagonal entry being the degree of the corresponding vertex of directed graph G. Then the matrix L(G) = D(G) − A(G) is called the Laplacian matrix of G. Since a directed graph has two types of degrees namely indegree and outdegree, they result in directed graphs also having the both types of its Laplacian matrices. In this study, the adjacency matrix and the Laplacian matrix of cyclic directed prism graph are investigated. The general form of the coefficients of polynomial characteristic of the Adjacency matrix and Laplacian matrix, respectively is obtained by applying the row reduction method in linear algebra, whereas the general form of the eigenvalues of the polynomial characteristic of the Adjacency matrix and Laplacian matrix, respectively is obtained by factorization and substitution methods.

Semigraph was defined by Sampathkumar as a generalization of a graph. In this paper the adjacency matrix which represents semigraph uniquely and a characterization of such a matrix is obtained. An algorithm to construct the semigraph from a given square matrix, if semigraphical is given. Some properties of adjacency matrix of semigraph are studied. A sufficient condition for eigen values to be real is also obtained.

Let G = (V,E), V = {1,2, …, n}, be a simple graph of order n and size m, without isolated vertices. Denote by d1 ≥ d2 … ≥ dn > 0, di = d(i), a sequence of its vertex degrees. If vertices i and j are adjacent, we write i ~ j. With TI we denote a topological index that can be represented as TI = TI(G) = Σi~j F(di,dj), where F is an appropriately chosen function with the property F(x,y)=F(y,x). Randic vertex-degree-based adjacency matrix RA=(ri j) is defined as rij = Fp(di,dj) √didj, if i ~ j, and 0 otherwise. Denote by f1 ≥ f2 ≥ … ≥ fn the eigenvalues of RA. Upper and lower bounds for fi, i = 1,2, … n are obtained.

In Section 4 of the original paper ‘Complex adjacency matrix and energy of digraphs’, we incorrectly asserted that the iota energy of digraphs increases with respect to the quasi-order rela...

This research paper studies about the adjacency matrix of a graph, as it is a fundamental matrix associated with any graph. This study about the properties of adjacency matrix and associated theorems is inevitable since the graph is stored in a computer in terms of its adjacency matrix.

In this article, we analyze the limiting eigen-value distribution (LED) of random geometric graphs (RGGs). The RGG is constructed by uniformly distributing n nodes on the d-dimensional torus $\Gamma^{d}\equiv [0, 1]^{d}$ and connecting two nodes if their $\ell_{p}$-distance, $ p\in [1,\ \infty]$ is at most r n . In particular, we study the LED of the adjacency matrix of RGGs in the connectivity regime, in which the average vertex degree scales as $\log(n)$ or faster, i.e., $\Omega(\log(n))$. In the connectivity regime and under some conditions on the radius r n , we show that the LED of the adjacency matrix of RGGs converges to the LED of the adjacency matrix of a deterministic geometric graph (DGG) with nodes in a grid as n goes to infinity. Then, for n finite, we use the structure of the DGG to approximate the eigenvalues of the adjacency matrix of the RGG and provide an upper bound for the approximation error. Index Terms--Random geometric graphs, adjacency matrix, limiting eigenvalue distribution, Levy distance.

A prism graph is a graph which corresponds to the skeleton of an n-prism and therefore it is a cyclic simple graph. It is denoted Yn (n ≥ 3) where n is half the number of vertices. An n-prism graph has 2n vertices and 3n edges. In this paper, only regularly-directed cyclic prism graphs are investigated. The anti-adjacency matrix is applied as the graph representation. An anti-adjacency matrix of graph representation is a 0–1 matrix of size m × m where m is the number of vertices. The entry bij of an anti-adjacency matrix B(G) of directed graph G is 0 if there exists a directed edge from vertex vi to vertex vj and is 1 otherwise. The characteristic polynomial of the anti-adjacency matrix B(Yn) of directed cyclic prism graph Yn are obtained. The characteristic polynomial will be proved by observing the both cyclic and acyclic induced subgraphs of the directed cyclic prims graph. Furthermore, the anti-adjacency matrix of directed cyclic prism graph is found to have both real eigenvalues and complex eigenvalues which appear in conjugate pairs.

The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, \(\mathcal F\), of graphs. In general the family \(\mathcal F\) is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define \(\mathcal F\), we take algebraic route. More formally, given a fixed positive integer r, we define \(\mathcal{F}_r\) as the family of graphs where for each \(G\in \mathcal{F}_r\), the rank of the adjacency matrix of G is at most r. Using the family \(\mathcal{F}_r\) we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: \(r\)-Rank Vertex Deletion, \(r\)-Rank Edge Deletion and \(r\)-Rank Editing. These problems generalize the classical Vertex Cover problem and a variant of the d -Cluster Editing problem. We first show that all the three problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time \(2^{\mathcal{O}(k \log r)}n^{\mathcal{O}(1)}\) for \(r\)-Rank Vertex Deletion, and an algorithm for \(r\)-Rank Edge Deletion and \(r\)-Rank Editing running in time \(2^{\mathcal{O}(f(r) \sqrt{k} \log k )}n^{\mathcal{O}(1)}\). We complement our FPT result by designing polynomial kernels for these problems.

Let G be a graph. An edge orientation of G is called smooth if the in-degree and the out-degree of every vertex differ by at most one. In this paper, we show that if G is a 2-edge-connected non-bipartite graph with δ ( G ) ≥ 3 , then G has a smooth primitive orientation. Among other results, using the spectral radius of digraphs, we show that if D 1 is a primitive regular orientation and D 2 is a non-regular orientation of a given graph, then for sufficiently large t, the number of closed walks of length t in D 1 is more than the number of closed walks of length t in D 2 .

19 April 2022 A Correction to this paper has been published: https://doi.org/10.1007/s42979-022-01141-w [Abstract] Computing the product of the (binary) adjacency matrix of a large graph with a real-valued vector is an important operation that lies at the heart of various graph analysis tasks, such as computing PageRank. In this paper, we show that some well-known webgraph and social graph compression formats are computation-friendly, in the sense that they allow boosting the computation. We focus on the compressed representations of (a) Boldi and Vigna and (b) Hernández and Navarro, and show that the product computation can be conducted in time proportional to the compressed graph size. Our experimental results show speedups of at least 2 on graphs that were compressed at least 5 times with respect to the original. We thank Cecilia Hernández for providing us with her software extracting the bicliques, and a helpful description in how to run it. This research has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie [grant agreement No 690941], namely while the first author was visiting the University of Chile, and while the second author was affiliated with the University of Helsinki and visiting the University of A Coruña. The first author was funded by Fundação para a Ciência e a Tecnologia (FCT) [grant number UIDB/50021/2020 and PTDC/CCI-BIO/29676/2017]; the second author was funded by the Academy of Finland [Grant number 268324], Fondecyt [Grant number 1171058] and NSERC [Grant number RGPIN-07185-2020]; the third author was funded by JSPS KAKENHI [grant numbers JP21K17701 and JP21H05847]; the fourth author was funded by AEI and Ministerio de Ciencia e Innovación (PGE and FEDER) [grant number PID2019-105221RB-C41] and Xunta de Galicia (co-funded with FEDER) [Grant numbers ED431C 2021/53 and ED431G 2019/01]; and the fifth author was funded by ANID – Millennium Science Initiative Program – Code ICN17_002 Xunta de Galicia; ED431C 2021/53 Xunta de Galicia; ED431G 2019/01

In this paper, we found the Moore-Penrose generalized inverse of adjacency matrix of an undirected graph, explicitly. We proved that the matrix $R_\lambda= [r_{ij}]$ is nonsingular where $r_{ii}=\frac{1}{\lambda}+ \deg v_i$ and $r_{ij}=\mid N_G(V_i)\cap N_G(V_j)\mid$ for $i\neq j$, and we proved that $A^{\dagger}_G=[s_{ij}]_{1\leq i, j \leq n}$ where $\displaystyle{s_{ij}=s_{ji}=\lim_{\lambda \rightarrow +\infty} \langle R^{-1}_{\lambda}e_j, f_i \rangle }$. The proof of the main result was based on the Tikhonov regularization., Comment: 6, articles

A mixed graph is a graph with edges and arcs, which can be considered as a hybrid of an undirected graph and a directed graph. In this paper we define the mixed adjacency matrix and the mixed energy of a mixed graph. The mixed adjacency matrix generalizes both the adjacency matrix of an undirected graph and the skew-adjacency matrix of a digraph. Then we compute the characteristic polynomial of the mixed adjacency matrix of a mixed graph and deduce some basic results from it. Furthermore, we give bounds to the mixed energy of a general mixed graph, and we compute the mixed energy of some special mixed graphs. At the end of the paper, we introduce mixed unitary Cayley graphs and compute their spectra.