Related Experiment Video
Updated: Jul 16, 2026
07:35
A Knowledge Graph Approach to Elucidate the Role of Organellar Pathways in Disease via Biomedical Reports
Published on: October 13, 2023
Path matching and graph matching in biological networks.
1Department of Computer Science, Texas A and M University, College Station, Texas 77843, USA.
Summary
We developed efficient algorithms for biological network analysis, enabling the discovery of common substructures in protein interaction and metabolic networks. These tools improve upon previous methods for path and graph matching in large biological datasets.
Area of Science:
- Bioinformatics
- Computational Biology
- Network Science
Background:
- Biological networks, such as protein-protein interaction and metabolic networks, are crucial for understanding cellular processes.
- Identifying common substructures within these networks can reveal evolutionary patterns and functional relationships.
- Existing algorithms for path and graph matching in biological networks often rely on computationally expensive or less accurate methods.
Purpose of the Study:
- To develop novel, efficient algorithms for path and graph matching in biological networks.
- To enable the identification of biologically meaningful substructures within large-scale biological networks.
- To provide accurate and computationally feasible tools for analyzing the evolution of biological networks.
Main Methods:
- Developed algorithms for path matching by reducing it to finding the longest weighted path in a directed acyclic graph.
- Solved the problem of finding top k suboptimal paths in polynomial time, improving upon exponential time algorithms.
- Reduced graph matching to finding highest scoring subgraphs and provided an exact algorithm for moderately sized query graphs.
- Validated algorithms on protein interaction networks (DIP database) and metabolic networks (KEGG database).
Main Results:
- Demonstrated the ability to extract biologically meaningful pathways from real-world biological network data.
- Achieved polynomial time complexity for finding top k suboptimal paths, significantly improving efficiency.
- Provided an exact algorithm for graph matching, avoiding the need for heuristic or randomized approaches.
- Successfully identified relevant substructures in protein interaction and metabolic networks.
Conclusions:
- The developed PathMatch and GraphMatch algorithms offer efficient and accurate solutions for path and graph matching in biological networks.
- These algorithms facilitate the study of common substructures, aiding in the understanding of network evolution.
- The software is publicly available, promoting further research in computational biology and bioinformatics.
Related Concept Videos
02:26Protein Networks
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
02:26Protein Networks
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
02:04Protein-protein Interfaces
Many proteins form complexes to carry out their functions, making protein-protein interactions (PPIs) essential for an organism's survival. Most PPIs are stabilized by numerous weak noncovalent chemical forces. The physical shape of the interfaces determines the way two proteins interact. Many globular proteins have closely-matching shapes on their surfaces, which form a large number of weak bonds. Additionally, many PPIs occur between two helices or between a surface cleft and a polypeptide...
01:29Primary Active Transport
In contrast to passive transport, active transport involves a substance being moved through membranes in a direction against its concentration or electrochemical gradient. There are two types of active transport: primary active transport and secondary active transport. Primary active transport utilizes chemical energy from ATP to drive protein pumps embedded in the cell membrane. With energy from ATP, the pumps transport ions against their electrochemical gradients—a direction they would not...