Recent Developments in Chemical Graph Theory and Graphical Bioinformatics
Presented by Prof. Milan RANDIć
Type: Keynote Lecture
Chemical Graph Theory is concerned with analysis of chemical data using Discrete Mathematics and Graph Theory. Graphical Bioinformatics approaches problems of Bioinformatics by representing input data graphically and follows with their numerical analysis. We will consider recent developments in these areas including: (1) Novel graph matrices and novel graph invariants; (2) Graph theoretical calculation of ring currents in molecules; (3) Comparative study of maps focusing on proteomics maps; (4) Analytical solution to DNA and protein sequence alignments. RE 1: Novel graph matrices include the DMAX, the elements of which are the largest entries (entry) in each row and column of the distance matrix; and the Common Vertex matrix, the elements of which are given by the number of vertices at equal distance from vertices (i, j). Novel invariants include the ordered row sums and the sum over all atoms of the quotients of path/walk counts of the same length. RE 2: We will illustrate how enumerations of contributions of π-electron currents in conjugates circuits, which are of opposite direction in 4n+2 and 4n circuits, give results that are comparable to ab initio quantum chemical calculations of π -current densities. This opens fundamental question: How can discrete and continuous models yield similar results? RE 3: We consider the problem of canonical labels for map elements and will illustrate how information contained in a triplet (x, y, z) can be graphically represented as a 2D map using weighted Voronoi domains. Finally, RE 4: We will outline VESPA (Very Efficient Search for Protein Alignment) and VESNA (Very Efficient Search for Nucleotide Alignment), very recent exact analytical solutions to protein and DNA alignments, respectively, which awaited over 40 years to be found. All hitherto obtained solutions to the protein and DNA alignments have been based on use of computer algorithms, starting with: Needleman–Wunsch algorithm (1970), followed by Smith–Waterman algorithm (1981), and more efficient algorithms FASTA of David J. Lipman and William R. Pearson (1985) and BLAST (Basic Local Alignment Search Tool) by David J. Lipman et al. (1990).