Related Experiment Video
Updated: Jun 20, 2026
08:07
Probing High-density Functional Protein Microarrays to Detect Protein-protein Interactions
Published on: August 2, 2015
Investigations on Multiple Protein Scaffold Filling
Ismoiljon Muzaffarov1, Xiaowen Liu2, Letu Qingge3
1Gianforte School of Computing, Montana State University, Bozeman, Montana, USA.
Summary
This study addresses protein scaffold filling challenges. We developed algorithms to optimize Blosum62 scores for sequence filling, with promising heuristic results for specific protein types.
Area of Science:
- Computational Biology
- Bioinformatics
- Proteomics
Background:
- Protein scaffold filling is crucial for sequence reconstruction and analysis.
- Optimizing Blosum62 scores is key for accurate sequence alignment and comparison.
Purpose of the Study:
- To investigate computational problems in multiple protein scaffold filling.
- To develop algorithms for maximizing Blosum62 scores in sequence filling, with or without references.
Main Methods:
- Theoretical analysis of algorithmic complexity, including lower bounds based on the Strong Exponential Time Hypothesis (SETH).
- Development of a dynamic programming approach for solving the optimization problem in polynomial time for two or more scaffolds.
- Implementation of heuristic algorithms for the specific case of three scaffolds.
Main Results:
- A lower bound of Ω(n^(k-ε)) is established for finding k scaffolds, assuming SETH.
- A polynomial-time dynamic programming solution is presented for the general case with two or more scaffolds.
- Heuristic algorithms demonstrated promising empirical results on diverse protein datasets (antibody, myoglobin, etc.).
Conclusions:
- The computational complexity of protein scaffold filling is significant, with theoretical lower bounds established.
- Dynamic programming offers an efficient solution for multiple scaffolds, while heuristics provide practical approaches for specific cases.
- The developed methods and heuristics show potential for applications in protein sequence analysis and reconstruction.
Related Concept Videos
01:18Assembly of Cytoskeletal Filaments
Cytoskeletal filaments are polymeric forms of smaller protein subunits. However, individual cytoskeletal filaments may easily disassemble or associate with other similar filaments to form rigid structures. Microfilaments, made of actin monomers, rely on actin-binding proteins to form bundles and create networks of individual actin filaments. Microtubules rely on microtubule-associated proteins (MAPs) to form sturdy cylindrical structures. However, the proteins involved in forming complex...
01:30Assembly of Signaling Complexes
Multiprotein signaling complexes are formed in a dynamic process involving protein-protein interactions at the cytoplasmic domain of transmembrane receptors or enzymatic and non-enzymatic proteins associated with the receptor. These complexes ensure the activation and propagation of intracellular signals that regulate cell functions.
Interaction domains in cell signaling
Interaction domains recognize exposed features of their binding partners containing post-translationally modified sequences,...
Interaction domains in cell signaling
Interaction domains recognize exposed features of their binding partners containing post-translationally modified sequences,...
01:57Protein Complexes with Interchangeable Parts
Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
02:41Protein Complex Assembly
Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types. Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...
Many viruses self-assemble into a fully functional unit using the infected host cell to...
02:41Protein Complex Assembly
Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types. Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...
Many viruses self-assemble into a fully functional unit using the infected host cell to...
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,...