Related Experiment Video
Updated: Mar 24, 2026
13:56
A Comparative Approach to Characterize the Landscape of Host-Pathogen Protein-Protein Interactions
Published on: July 18, 2013
11.7K
Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-viral Infection Patterns.
Ilan Smoly1, Amir Carmel1, Yonat Shemer-Avni2
11 Department of Computer Science, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
Summary
This study introduces a new method for querying molecular interaction networks, extending pattern searches from paths to trees using regular tree grammars (RTGs). The developed algorithm efficiently finds top-scoring tree patterns, aiding in biological network analysis.
Area of Science:
- Computational Biology
- Bioinformatics
- Network Science
Background:
- Network querying is crucial for analyzing molecular interactions.
- Existing tools often lack topological flexibility or are limited to path identification.
- Grammar-based queries offer greater expressiveness for network pattern matching.
Purpose of the Study:
- To extend grammar-based network querying from paths to trees.
- To develop an algorithm for finding k-highest scoring tree subgraphs matching a regular tree grammar (RTG).
- To apply this method for mining viral infection patterns in molecular networks.
Main Methods:
- Utilized regular tree grammars (RTGs) as a higher-order query descriptor.
- Developed a novel algorithm combining dynamic programming with color coding.
- Incorporated an extension of k-best parsing to avoid isomorphic tree outputs.
Main Results:
- Successfully extended grammar-based querying to identify tree patterns in networks.
- The proposed algorithm efficiently searches for top-scoring subgraphs matching RTG patterns.
- Demonstrated application in identifying viral infection patterns within molecular interaction networks.
Conclusions:
- The novel algorithm provides a powerful tool for tree pattern discovery in biological networks.
- This approach enhances the flexibility and scope of grammar-based network querying.
- The implemented method and available code facilitate advanced analysis of molecular interactions.
Related Concept Videos
02:54Evolutionary Relationships through Genome Comparisons
7.2K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
7.2K
01:28Microbial Phylogeny
22
Understanding the evolutionary relationships among microorganisms is fundamental to microbial ecology and taxonomy. Phylogenetic trees are essential tools for inferring these relationships, relying primarily on comparative analyses of molecular sequences such as DNA, RNA, or proteins. In microbial studies, these trees typically depict the evolutionary paths of diverse bacterial and archaeal species by mapping genetic differences accumulated over time.Phylogenetic trees are composed of tips,...
22
00:36Viral Mutations
40.7K
A mutation is a change in the sequence of bases of DNA or RNA in a genome. Some mutations occur during replication of the genome due to errors made by the polymerase enzymes that replicate DNA or RNA. Unlike DNA polymerase, RNA polymerase is prone to errors because it is not capable of “proofreading” its work. Viruses with RNA-based genomes, like HIV, therefore accrue mutations faster than viruses with DNA-based genomes. Because mutation and recombination provide the raw material...
40.7K
01:29Viruses with RNA Genomes
1.2K
RNA viruses are categorized into positive-strand, negative-strand, or double-stranded groups based on their genomic structure and replication mechanisms. This classification dictates how they exploit host cellular machinery for protein synthesis and replication. Some RNA viruses also utilize reverse transcription as part of their life cycle, further diversifying their replication strategies.Positive-Strand RNA VirusesPositive-strand RNA viruses have genomes that function directly as messenger...
1.2K
01:26Size and Structure of Viral Genomes
1.0K
Viral genomes exhibit remarkable diversity in size, structure, and composition, influencing their replication strategies and interactions with host cells. These genomes consist of either DNA or RNA and may be linear or circular. Additionally, they can be single-stranded or double-stranded, with each configuration affecting how the virus propagates within a host. RNA viruses, for instance, generally have smaller genomes than DNA viruses, a factor that contributes to their high mutation rates and...
1.0K
01:26Human Virome
32
The human body harbors a vast and diverse viral community known as the human virome. The virome includes bacteriophages that infect bacteria, and eukaryotic viruses that infect human cells. Transient dietary and environmental viruses also contribute to this dynamic ecosystem. Estimates suggest the human body may contain on the order of 10¹³ viral particles, though abundance varies widely by body site and detection method.Comprehensive characterization of the virome has become possible...
32