Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Protein Networks02:26

Protein 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,...
Protein Networks02:26

Protein 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,...
Protein-protein Interfaces02:04

Protein-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...
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving01:29

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Modern Molecular Taxonomy01:29

Modern Molecular Taxonomy

Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Combining Clickstream Analyses and Graph-Modeled Data Clustering for Identifying Common Response Processes.

Psychometrika·2021
Same author

Stable roommates with narcissistic, single-peaked, and single-crossing preferences.

Autonomous agents and multi-agent systems·2020
Same author

Matching algorithms for assigning orthologs after genome duplication events.

Computational biology and chemistry·2018
Same author

Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems.

Methods in molecular biology (Clifton, N.J.)·2016
Same author

Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage.

IEEE/ACM transactions on computational biology and bioinformatics·2015
Same author

A graph modification approach for finding core-periphery structures in protein interaction networks.

Algorithms for molecular biology : AMB·2015
Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024
See all related articles

Related Experiment Video

Updated: Jun 4, 2026

JUMPn: A Streamlined Application for Protein Co-Expression Clustering and Network Analysis in Proteomics
07:28

JUMPn: A Streamlined Application for Protein Co-Expression Clustering and Network Analysis in Proteomics

Published on: October 19, 2021

Parameterized algorithmics for finding connected motifs in biological networks.

Nadja Betzler1, René van Bevern, Michael R Fellows

  • 1Institut für Softwaretechnik und Theoretische Informatik, Technische Universtität Berlin, 10587 Berlin, Germany. nadja.betzler@campus.tu-berlin.de

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|February 2, 2011
PubMed
Summary
This summary is machine-generated.

We developed algorithms for the LIST-COLORED GRAPH MOTIF problem, crucial for analyzing biological networks. Our methods efficiently find network motifs with specific color requirements, proving useful in protein-interaction network analysis.

More Related Videos

Genome-wide Protein-protein Interaction Screening by Protein-fragment Complementation Assay (PCA) in Living Cells
08:38

Genome-wide Protein-protein Interaction Screening by Protein-fragment Complementation Assay (PCA) in Living Cells

Published on: March 3, 2015

Related Experiment Videos

Last Updated: Jun 4, 2026

JUMPn: A Streamlined Application for Protein Co-Expression Clustering and Network Analysis in Proteomics
07:28

JUMPn: A Streamlined Application for Protein Co-Expression Clustering and Network Analysis in Proteomics

Published on: October 19, 2021

Genome-wide Protein-protein Interaction Screening by Protein-fragment Complementation Assay (PCA) in Living Cells
08:38

Genome-wide Protein-protein Interaction Screening by Protein-fragment Complementation Assay (PCA) in Living Cells

Published on: March 3, 2015

Area of Science:

  • Computational biology
  • Graph theory
  • Algorithm design

Background:

  • Biological network analysis often involves identifying recurring patterns or motifs.
  • The LIST-COLORED GRAPH MOTIF problem is essential for finding these motifs within networks where nodes have associated colors.
  • Existing computational methods face challenges with efficiency and scalability for complex biological networks.

Purpose of the Study:

  • To develop and analyze efficient algorithms for the NP-hard LIST-COLORED GRAPH MOTIF problem.
  • To investigate the problem's complexity under different parameterizations, specifically motif size (|M|) and solution size (|S|).
  • To demonstrate the practical applicability of these algorithms in analyzing real-world biological networks, such as protein-interaction networks.

Main Methods:

  • Fixed-parameter tractable algorithms were designed for the motif size (|M|) and solution size (|S|) parameters.
  • W[1]-hardness was proven for the parameter |V| - |M| in general instances, with fixed-parameter tractability shown for a special case.
  • Implementation of the fixed-parameter algorithms and development of speed-up heuristics were performed.
  • The algorithms were applied to protein-interaction networks to assess their performance on realistic data.

Main Results:

  • Fixed-parameter algorithms for |M| and |S| were successfully developed and implemented.
  • The study identified W[1]-hardness for a specific parameterization, while achieving tractability for a related subproblem.
  • Demonstrated the practical utility of the algorithms in analyzing protein-interaction networks, highlighting their efficiency and effectiveness.
  • Investigated the impact of increased connectivity requirements (biconnectedness, bridge-connectedness), revealing their computational complexity.

Conclusions:

  • The developed fixed-parameter algorithms offer efficient solutions for the LIST-COLORED GRAPH MOTIF problem in biological network analysis.
  • The complexity analysis provides insights into the problem's inherent difficulty under various parameterizations.
  • The practical application in protein-interaction networks validates the algorithms' usefulness for real-world biological data.
  • Stricter connectivity demands significantly increase the computational complexity of motif finding.