Discrete Kernels

Kernels play a crucial role in analyzing biological networks, from DNA sequences to protein structures. Count Kernel efficiently counts k-mers, while Graph Kernels define functions for labeled vertices and edges. Path-probability vectors and marginalized kernels further enhance graph analysis methods. Explore the use of kernels in classifying protein 3D structures and understanding complex biological networks induced from sequence similarity. Dive into cutting-edge methods for graph analysis beyond traditional frameworks.

• Graph Kernels
• Biological Networks
• Protein Structures
• DNA Sequences
• Path-probability

kuma_fo Follow

Uploaded on Feb 27, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Discrete Kernels

2. Kernels for Sequences Similarity between sequences of different lengths ACGGTTCAA ATATCGCGGGAA 2

3. Count Kernel Inner product between symbol counts Extension: Spectrum kernels (Leslie et al., 2002) Counts the number of k-mers (k-grams) efficiently 3

4. Motivations for graph analysis Existing methods assume tables Serial Num Name Age Sex Address 0001 40 Male Tokyo 0002 31 Female Osaka Structured data beyond this framework New methods for analysis 4

5. Graph Structures in Biology DNA Sequence Compounds A C G C H C RNA UA C C H H O CG C C H C CG H H U U U U 5

6. Graph Kernels (Kashima, Tsuda, Inokuchi, ICML 2003) Going to define the kernel function Both vertex and edges are labeled 6

7. Label path Sequence of vertex and edge labels Generated by random walking Uniform initial, transition, terminal probabilities 7

8. Path-probability vector 8

9. Kernel definition Kernels for paths Take expectation over all possible paths! Marginalized kernels for graphs 9

10. Classification of Protein 3D structures Graphs for protein 3D structures Node: Secondary structure elements Edge: Distance of two elements Calculate the similarity by graph kernels 10 Borgwardt et al. Protein function prediction via graph kernels , ISMB2005

11. Biological Networks Protein-protein physical interaction Metabolic networks Gene regulatory networks Network induced from sequence similarity Thousands of nodes (genes/proteins) 100000s of edges (interactions) 11

12. Physical Interaction Network Undirected graphs of proteins Edge exists if two proteins physically interact Docking (Key Keyhole) Interacting proteins tend to have the same biological function 12

13. Metabolic Network 13

14. Diffusion kernels (Kondor and Lafferty, 2002) Function prediction by SVM using a network Kernels are needed ! Define closeness of two nodes Has to be positive definite How Close? 14

15. Definition of Diffusion Kernel A: Adjacency matrix, D: Diagonal matrix of Degrees L = D-A: Graph Laplacian Matrix Diffusion kernel matrix Diffusion paramater Matrix exponential, not elementwise exponential 15

16. Computation of Matrix Exponential Definition Eigen-decomposition 16

17. Adjacency Matrix and Degree Matrix 17

18. Graph Laplacian Matrix L 18

19. Actual Values of Diffusion Kernels Closeness from the central node 19