iGEM 2024 — Team iisc-software

{% extends "layout.html" %} {% block title %}Notebook{% endblock %} {% block
lead %}{% endblock %} {% block page\_content %}

Our iGEM journey has been an exciting blend of ideation, problem-solving,
and consistent progress. From the initial stages in June to our current
strides in September, we've worked hard to bring our vision of IMPROViSeD to
life. Below is a detailed reflection on the key moments from March through
September, where we highlight the pivotal tasks, decisions, and milestones
that shaped our project.

# March — June

**Ideation and Exploration.**
The early months were all about brainstorming and exploring different
directions. From March to June, we rigorously debated potential projects,
experimenting with ideas like predicting metal-binding proteins and
genome-wide miRNA prediction. These discussions gave us critical insight
into various possibilities, but it wasn't until late June that we began to
narrow our focus toward protein complexes and integrated modelling platforms,
an area that would soon give rise to IMPROViSeD.

# July

**Settling on IMPROViSeD and Laying the Groundwork.**
With July, came a burst of momentum. Our team finalized the IMPROViSeD
platform, which centered on using experimental cross-linking data for
modelling protein complexes. We now had a solid direction, and the task ahead
was to bring this platform to life.

## Week of 14th July

The first week after our decision was focused on ensuring the
**responsiveness of our web page** to make it user-friendly and
accessible, and this is where we started laying the foundations of our wiki.
Meanwhile, we also worked on the **team logo** design, a crucial part of
our identity, and made strides in planning an
**educational app for computational biology** to engage with younger
audiences. While the designs were still being refined, the core framework of
the project was coming together, and our **registration code** for
modelling went through its initial phase of implementation.

## Week of 21st July

Alongside technical progress, we were actively engaging in outreach. Our
**school visits** were postponed this week, but we kept busy with
presentations on **GPCRs** (we were yet to finalize the wet lab aspects
of the project), adding to our educational efforts and refining our
storytelling abilities for future workshops. These talks were intended to help us
present our scientific ideas in a more accessible format.

## Week of 28th July

The final week of July saw us diving into full-scale **workshops**. We
also participated in the **AIIM judging session** (we presented our
project to a panel of judges comprising field experts and iGEM ambassadors
and also a poster to the congregation) while mapping out a detailed plan for
our upcoming experimental procedures. Additionally, we began a
**literature review** focused on AI-based functional prediction of
proteins and expanded our documentation efforts for future use. This was
also the week when our coding team refined
**EDMC (Eucledian Distance Matrix Completion)** methods and focused on
**geometric refinement** for the protein models.

# August

**Refining the Platform and Expanding Our Reach.** August was a month of
refining our technical workflows and enhancing outreach efforts.

## Week of 4th August

We began the creation of our **Project Promotion Video**, a crucial step
in communicating our vision to the broader iGEM audience. This week also
included a visit to **NPS Rajajinagar School**, where we connected with
students, sparking interest in synthetic biology. On the technical front,
the team continued refining the **EDMC methods**, overcoming some initial
challenges and progressing with **geometric refinement**, ensuring the
stability of our model.

## Week of 11th August

The middle of August was marked by the organization of a **hackathon**,
where we brainstormed contact lists, platforms, and problem statements. This
gave our project a fresh burst of energy. Concurrently, we focused on
completing important forms, like the **safety forms** and
**team page updates**. In terms of coding, we made strides with
**refinement II** for our modelling methods, making the system more
robust.

## Week of 18th August

By the third week of August, we had successfully completed the second round
of **CLI refinement** (the BEPT tool). Meanwhile, we tackled the final
stages of the hackathon, making sure everything was in place for a smooth
experience. Documentation was also underway, with updates on the safety and
attribution forms.

## Week of 25th August

The last week of August was a productive one. We integrated a
**SDP (Semi-Definite Program) Solver** into the platform, further
enhancing its functionality. This week also involved refining our
**safety form submission**, ensuring that all necessary precautions were
meticulously documented and in line with iGEM requirements. This is also
where we had finalized on our wet lab aspects and discussed with
**Dr. Manjula Das** regarding protein availability.

# September

**The Final Push.** September marked the final stretch, where everything
started coming together.

## Week of 1st September

The first week of the month was marked by the submission of our
**final safety form** and the **Project Promotion Video**. This was a
significant milestone, as it marked the completion of key deliverables for
the competition. We focused heavily on getting the video ready, making sure
that it visually captured our journey and the core ideas behind IMPROViSeD.

## Week of 8th September

With the video submitted, we turned our attention toward the
**team roster** and polishing the final theme design. The homepage design
was crafted with care, bringing to life the essence of our project.
Simultaneously, the **attribution and documentation process** began,
making sure that every contribution was properly acknowledged and recorded
for the final submission. We received the **LCN2 Protein** this week and
began standardizing the in-gel digestion protocol. The software team was
focusing on post-processing steps.

## Week of 15th September

Mid-September was all about field visits and visual presentation. We
organized an **industry and clinic visit**, aimed at bridging the gap
between our theoretical work and real-world applications. A
**team photo** was also taken, which would be used on our website.

## Week of 22nd September

As the month drew to a close, we entered the final phase of preparations.
**Attribution forms, judging forms, and software submissions** were all
tackled with care and precision, ensuring that nothing was left incomplete.
The documentation effort also intensified, with every element being
thoroughly reviewed and refined. The post-processing steps for the software
were nearing completion. The **mass spectrometry data** for the in-gel
digested peptide was available from the mass spectrometry facility at IISc.
We also received **MMP9** this week and began standardizing the
cross-linking experiments.

## Week of 29th September

The final week was all about polishing and validating our work. We focused
on optimising the results, making sure that our platform was ready for the
judges. The last push toward submission involved wrapping up documentation,
preparing final validation results, and ensuring that all loose ends were
tied up.

# October

**Conclusion.** From ideation to execution, each phase of our project has
been crucial in shaping IMPROViSeD into a powerful tool for understanding
protein complexes. Our journey through these months reflects the hard work,
collaboration, and dedication of each team member. As we enter the final
stages of the competition, we're excited to present our work and demonstrate
the impact of our platform.

![Fuelling up for the final push! Midnight pizza party as we review and put the finishing touches on our wiki, just hours before the submission deadline.](https://static.igem.wiki/teams/5346/cfa93407-1b04-416b-ac66-38e42eb6530d.jpg)

Fuelling up for the final push! Midnight pizza party as we review and put the finishing touches on our wiki, just hours before the submission deadline.

{% endblock %}

{% extends "layout.html" %} {% block title %}Engineering{% endblock %}
{% block lead %}{% endblock %} {% block page\_content %}

# Challenges in Integrated Modelling

The conundrum lies in the computational cost incurred in modelling three-dimensional structures for protein
complexes.

* The challenges stem from sampling the entire space of valid protein conformations for instances
  that satisfy the experimental evidence.
* Under-sampling of the conformational space risks missing one or more valid solutions. This may
  have far-reaching consequences.
* A conservation approach is therefore adopted by beginning with a sizable number, say \(k\), of
  initial orientations for the protein sub-units forming the complexes. The guess must be randomly
  selected across the space of valid protein conformations. This is easier said than accomplished.
  Indeed, a large volume of work exists to sample this space.

Each of these is successively improved to decrease the system’s potential energy. The goal is that the
conformation with the lowest energy is a thermodynamically stable state. However, the underlying
computations involve deriving a new position for each of the atoms involved, as they are perturbed in
each iteration. Recall that even for a moderately sized protein, the number of atoms can be in tens of
thousands. The computational overhead is further compounded by the fact that:

* While parallel computations are employed to mitigate the overhead, the increased demands on the
  computational resources are substantially large.
* Each run originating from a single guess results in an ensemble of protein structures.
* Branch and bound and/or clustering methods are designed to quell the exponential increment of the
  solutions space.

The factors combine together to make the protein modelling problem beyond the reach of modest user with
limited resources. This includes handheld devices or edge computing.

# Motivation

* Why random guesses when data says otherwise. We intend to find initial orientations such that the
  experimental evidence is satisfied.
* How sensitive are the relative orientations of the proteins, given errors in the experimentally derived
  crosslinks?
* How sensitive are the relative orientations of the protein molecules for tailor-made contact points?
* If multiple orientations are possible? Can we predict new interfaces if they can be obtained with
  limited computation cost? This would be useful in artificial drug design.

# Method

## Conceptualize (Cycle-1)

![](https://static.igem.wiki/teams/5346/eng-images/wood-puzzle.png)

Puzzle to align pieces of wood such that thin struts between them fall into specific
notches.

Let’s solve a puzzle. Blocks of wood must be placed adjacent but not clash with each other. To aid the mutual
orientations, thin pegs of wood must snugly fit in their respective notches in the individual pieces. In
essence, the puzzle involves,

1. Bring two bodies together such that they do not deform.
2. Orientate them such that separation between certain anchor points remains fixed.
3. Perform minor adjustments so that any errors are ironed out.

Where else are similar problems found?

* Multiview registration
* DREAM
* Sensor network localization
* Robot position determination

We now revisit the problem of protein complex modelling from the experimental data. The inputs include:

1. Three-dimensional coordinate files for the subunits of the protein complex.
2. Experimental evidence, i.e., the crosslink file indicating the residues belonging to different
   subunits that are proximal to each other. The cutoff distance depends on the experimental setup.

We now formalize the mathematical construct for the problem so that we can analytically investigate the
various steps involved.

## Mathematical modelling

**Distance preserving transformation**

One of the first steps is to characterize the set of transformations that the individual subunits have to
undergo. Note that they should not suffer any deformation. In other words, the subunits must behave as
rigid bodies. Any transformation that the rigid bodies undergo must preserve their internal structure,
i.e., inter-atomic distance between points belonging to a single subunit must remain fixed.

![](https://static.igem.wiki/teams/5346/engineering-images/engineering-pic.jpg)

Problems similar to complex modelling. Multiview registration attempts to stitch images together (B) using different camera poses (A). LIDAR data is used in autonomous vehicles to simultaneously estimate their position with respect to its surroundings as shown in (C). DREAM uses the bottom-up strategy of modelling sub-structures before registering them into a single structure.

It can be shown mathematically that only rigid body motion, composed of rotation/reflection and translation quality for distance preserving transformation. The space of the rigid body orientations is well known to
form a special set in mathematics known as the in \(3\)D, denoted by \(\mathbb{SE}(3)\).
The set belongs to a larger class known as differential manifold. This is a generalization of euclidean space in higher dimensions.
Differentiation operation may be defined on such a set, and
consequently, one may model mathematical algorithms to directly optimize on \(\mathbb{SE}(3)\).
In other words, the problem of deriving optimal rigid motion, can be directly defined on
\(\mathbb{SE}(3)\). Indeed, a large volume of literature exists in this regard.

For our purpose of deriving a \(3\)D structure for the complex, each of the subunits is
considered a rigid body. The crosslinks form the upper bounds in distance, which need to be satisfied
when the subunits are aligned together.

\(\mathbb{SE}(3)\) is composed of the Cartesian product of two sets, one being the set of
rotations in \(3\)D (\(\mathbb{SO}(3)\)) and seconds being the space of \(3\)D
coordinates itself (\(\mathbb{R}^3\)). Formally, $$\mathbb{SE}(3) = \mathbb{SO}(3) \ltimes
\mathbb{R}^3$$We use this concept to break our problem of complex modelling into two steps. In
essence, the computation of optimal mutual orientation between the subunits (each orientation belonging
to \(\mathbb{SE}(3)\)) is broken down into two steps. First, an optimization module is designed
over the Cartesian coordinate \(\mathbb{R}^3\). The second is over the rotation group
\(\mathbb{SO}(3)\).

## Implementation (Cycle-2)

The underlying idea is to model a hypothetical structure consisting of only the C\(^\alpha\)
atoms from various subunits involved in the crosslinks. Synonymous with the wooden puzzle in Fig. [2.1](#woodpuzzle), the support
structure forms a scaffold for the subunits to attach with.

### Localization

Let \(C\_1\) and \(C\_2\) be the C\(^\alpha\) atoms from subunit-\(1\) and
\(2\) involved in the crosslinks. Since the structures of subunits are known, we derive a set of
equality bounds between any pair of atoms belonging to \(C\_1\) or \(C\_2\). Let the
equality bound be denoted by \(\mathcal{E}\_1\) and \(\mathcal{E}\_2\). Let the pairs of
atoms forming crosslinks be denoted by \(\mathcal{L}\_{12}\) and the magnitude be \(c\). We
want to compute a \(3\)D coordinates \(\left\{x\_i \right\}\_{i \in C\_1 \cup \, C\_2}\), such
that the distance constraints are satisfied.

Mathematically,
\[\label{localizationprob}
\begin{aligned}
\mathrm{Find} &\left\{x\_i \right\}\_{i \in C\_1 \cup \, C\_2}\\
\text{subject to} &\quad \|x\_i - x\_j \|\_2^2 = d^2\_{ij} \quad & (i,j) \in \mathcal{E}\_1
\cup \mathcal{E}\_2\\
&\quad \|x\_i - x\_j \|\_2^2 \leqslant \underline{c}^2 \pm \sigma \quad & (i,j) \in
\mathcal{L}\_{12}
\end{aligned}\]

Here, \(\sigma\) is randomly drawn from a normal distribution \(\mathcal{N}(0,\mu)\) to
denote the uncertainty of assigning a particular value to the magtitude of the crosslink. The
mathematical therefore models the noise in the experimental data. The problem can be shown to be reduceable to a more general problem of Graph Embedding in \(3\)D. This was shown to be NP-hard,
i.e., computationaly intractable in polynomial time . Hence we look for indirect approaches to estimate the solution
of problem.

Consider a Euclidean distance matrix \(D\). Each cell in the matrix is the distance between a
pair of atoms. Refer to fig provided below.
The matrix can be divided into two blocks. The lilac and green block contain the equality bounds between
the C\(^\alpha\) atoms belonging to \(C\_1\) and \(C\_2\). The white blocks are empty
except for the pairs, for which the upper bound can be found in the list of crosslinks
\(\mathcal{L}\_{12}\). The matrix there incomplete.

Techniques such as review in (6th Citation), establish
approaches to approximate a complete distance matrix, say \(\tilde{D}\), which best approximates
the entries defined in \(D\). We found it  prone to errors for sparse data, i.e., for a smaller
number of C\(^\alpha\) atoms, whereas Sci-py performed significantly better. Interestingly, the
trend was found to be the opposite if more atoms were involved. Since the number of crosslinks was in
the order of \(10\)-\(12\), Sci-py was found to work best empirically.

We can then derive the coordinates \(X = \left\{x\_i \right\}\_{i \in C\_1 \cup \, C\_2}\) from
\(\tilde{D}\) by two steps:

* We derive \(\tilde{X}\) by Cholesky’s decomposition  of \(\tilde{D}\), i.e., $$\tilde{D} = \tilde{X}^\top
  \tilde{X}$$
* Note that if \(\tilde{D}\), were a complete matrix, we would have obtained
  \(\tilde{X}\) as \(3\)D coordinates. However, since it is incomplete there are no
  such guarantees. In fact, for lower number of crosslinks, or ambiguities in them,
  \(\tilde{X}\) belongs to a higher dimension.
* We project \(\tilde{X}\) back to \(3\)D space by solving the problem \[\begin{aligned}
  \underset{X}{\mathrm{min}} \quad&\|X - \tilde{X}\|\_F^2 \\
  \text{subject to} \quad& \mathrm{rank}(X) = 3.
  \end{aligned}\]
  This is the well-known Young-Egkart theorem
  and has a closed-formed solution by the singular value decomposition of \(\tilde{D}\).

![](https://static.igem.wiki/teams/5346/eng-images/edmc.png)

Euclidean distance matrix (EDM). Each cell in the matrix denotes a pairwise distance making EDM
symmetric. While the coloured blocks are filled by equality bounds \(\mathcal{E}\_1,
\mathcal{E}\_2\), the white block is largely empty. Only crosslinks entries
\(\mathcal{L}\_{12}\) contribute to it. Localization problem can be modelled as completing
such an incomplete EDM. \(\sigma\) is a noise drawn from normal distribition
\(\mathcal{N}(0,\mu)\)

### Registration

Once the supporting structure(s) has been computed, we compute the optimal orientation of the subunits,
such that they attach to specified points in the supporting structure. The specific points to which the
subunits attaches themselves, if of course defined by the C\(^\alpha\) atoms which constitute the
supporting structure. However, the question remains, how does one find an optimal rigid body motion
(rotations, translations) which would align all the bodies together.

![](https://static.igem.wiki/teams/5346/1dfj-registration.png)

One shot Registration of protein with PDB ID 1DFJ. A hypothetical structure, shown with
coloured spheres correspoinding to the C\(^\alpha\) atoms in the two structure in similar
colour. Both the structures and the hypothetical structure aligns in a single step resulting in
the final structure.

### Pairwise versus global

![](https://static.igem.wiki/teams/5346/eng-images/pairwise.jpeg)

Consequences of Pairwise alignment , the image shows 4 sub units being resgistered (aligned) together by a sequence of pairwise alignment. Difference possibilities exist based on the sequence choosen, not all of which are valid protein structures. Thus one has to iterate through all the possibilities for the best result adding computational overhead.

A go to solution could be a sequence of pairwise alignments. A sequence of pairwise alignment leads to
the accumulation of errors. Further, the merging sequence is a combinatorial problem since all may not
lead to the same solution. Morevoer, the set of all rigid body motions, \(SE(3)\), is a
non-convex set. Hence optimization algorithms cannot be applied direct on such sets.

Let \(y\_i\) be the unknown coordinates of the PDB’s oriented together. Let \(x\_i\) be
coordinates of the individual PDB’s and the hypothetical structure computed in the localization stage.
Each of the PDB’s and the hypothetical structure under a rigid body motion (Rotation-\(R\_i\) and
translation-\(t\_i\)) such the C\(^\alpha\) atoms align together. We find a solution to the
following problem: \[\label{regeq}
\underset{y\_i, R\_k, t\_k} {\text{min}} \quad \sum\_{k=1}^m \quad \sum\_{i \in \mathcal{C}\_k} \|y\_i
- \left(R\_k x^k\_i + t\_k\right)\|\_2^2.\]

In general, directly computing solution over a set of rotation matrices is computationaly intractable
since it is a non-smooth non-convex set. However,
describes a global alignment approach following a non-linear optimization formulation known as
Semidefinite programmimng , to estimate a solution to
the following problem. The variables of equation are separated into \(\mathbb{R}^3\) and
\(\mathbb{O}(3)\). In order to circumvent the non-convexity of \(\mathbb{O}(3)\), a convex
progam is designed over a new variable \(G\) defined as \(G = R^\top R\), i.e, inner
product of rotation matrices. This has been employed in  as well to derive protein structure from NMR. We apply
similar approach to align the coordinates of the subunits and the supporting structure together.

## Flip Refinement (Cycle-3)

![](https://static.igem.wiki/teams/5346/eng-images/flip-1dfj-e-i.png)

Since, we are working with distance data alone, it is impossible to distinguish mirror images from each
other. Consider the registration problem. Consider two \(3\)D points \(y\) and
\(x\) such that they are related to each other by, \[\label{2bodyreg}
y = R x\]

such that \(R \in \mathbb{SO}(3)\). Define \(I\_{-1}\) as the identity matrix with a single
diagonal entry replaced by \(-1\). Note that \(I\_{-1} R\) is also a solution of equation.

In context of registration problem, the may lead to the chain I, as shown in (a) in the figure [above](#ramaflip). The corresponding Ramachandran map
for the chain I is shown in (d) in the figure [above](#ramaflip). Hence chain E is reflected as correction. This can be done
by noting the rotation matrix, say \(R\_{I}\) which was obtained from the registration step, and
multiplying any diagonal value by \(-1\). Thus determinant of \(R\_{I}\) will change sign,
indicating a reflection. The coordinates of chain I, acted upon the by the corrected \(R\_{E}\)
results shown in (c) in the figure [above](#ramaflip). The
corresponding Ramachandran map shown in (e) in the figure [above](#ramaflip). Note that no such corrections was required for chain E.

## Iterating (Cycle-4)

![](https://static.igem.wiki/teams/5346/exp-images/iterations.png)

Simplified Flowchart for IMPROViSeD. The subunits are oriented in multiple iterations. Each
resulting from a subset of crosslinks, followed by localization and registration. The iterations proceed in parallel. The
structures without clashes while satisfying the crosslinks gives final results.

Protein is a dynamic molecule. Their conformations undergo changes due to even minor flexibility of the
side chains or the main chain. In order to model such a scenario, we generate multiple conformations as
described in and summarized in Fig. [2.5](#flowchart). The number of crosslinks are varied in each run. Their
number were taken to vary between \(6\)-\(8\) for each case. The localization step may
lead to multiple solutions. In order to explore the space of valid conformational spaces, the
localization step was computed multiple times varying the seed value. The structures are then
registered. Note that each iteration is computationaly fast. Morevers, the executations can progress
parallely. This further reduces the computation time.

In order to prune the exponential increase of solution space, the structure are evaluated for crosslink
violations and clashes. The ones falling below a pre-determined thresshold are discarded. Also the whole
process terminates beyond a user defined number of iterations. The final structures obtaiend are ranked
on the basis of crosslink violation fraction and the energy score, using PyRosetta, computed for each of
them.

## Post-processing (Cycle-4)

Pseudocode for IMPROViSeD. Modelling three dimensional structures for protein complexes using crosslinking is broken down into two steps: Localization and Registration. The subunits are oriented in multiple iterations. Each results from a subset of crosslinks, followed by localiztion and registration. The iterations proceed in parallel. The structures with low crosslink violations and those that do not have clashes make it to as final result.

![](https://static.igem.wiki/teams/5346/eng-images/code11.png)

Psuedocode for IMPROViSeD. The subunits are oriented in multiple iterations. Each
resulting from a subset of crosslinks, followed by localization and registration. The iterations proceed in parallel. The
structures without clashes while satisfying the crosslinks gives final results.

We perform only a short EM (Energy minimization) step for a crude orientation. The user may choose to
employ detailed steps such as

* Side chain EM
* Main chain EM
* Simulated annealing

# References

1. Daniel Russel, Keren Lasker, Ben Webb, Javier Vel´azquez-Muriel, Elina Tjioe, Dina
   Schneidman-Duhovny, Bret Peterson, and Andrej Sali. Putting the pieces together: in-
   tegrative modelling platform software for structure determination of macromolecular as-
   semblies. PLoS Biol., 10(1):e1001244, January 2012.
2. Cyril Dominguez, Rolf Boelens, and Alexandre MJJ Bonvin. Haddock: a protein- pro-
   tein docking approach based on biochemical or biophysical information. Journal of the
   American Chemical Society, 125(7):1731–1737, 2003.
3. Serge Lang. Differential manifolds, volume 2. Springer, 1972.
4. Nathan Jacobson. Lie algebras. Courier Corporation, 2013.
5. Arnaud de Mesmay, Yo’av Rieck, Eric Sedgwick, and Martin Tancer. embeddability in
   R3 is NP-hard. SODA ’18, pages 1316–1329, 2018
6. Leo Liberti, Carlile Lavor, Nelson Maculan, and Antonio Mucherino. Euclidean distance
   geometry and applications. SIAM Review, 56(1):3–69, 2014.
7. Bamdev Mishra, Gilles Meyer, and Rodolphe Sepulchre. Low-rank optimization for distance matrix
   completion. In 2011 50th IEEE Conference on Decision and Control and
   European Control Conference, pages 4455–4460. IEEE, 2011.
8. Carl D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM, 2001.
9. K N Chaudhury, Y Khoo, and A Singer. Global registration of multiple point clouds using
   semidefinite programming. SIAM Journal on Optimization, 25(1):468–501, 2015.
10. Niladri R. Das, Kunal N. Chaudhury, and Debnath Pal. Improved nmr-data-compliant
    protein structure modelling captures context-dependent variations and expands the scope of
    functional inference. Proteins: Structure, Function, and Bioinformatics, 91(3):412–435,
    2023.
11. Niladri Ranajan Das, Kunal Narayan Chaudhury, and Debnath Pal. DREAMweb: An online tool for
    graph-based modelling of NMR protein structure. Proteomics, page e2300379,
    April 2024.
12. Zhang Yichi, Jindal Muskaan, Viswanath Shruthi, and Sitharam Meera. Integrative docking benchmark,
    2020

{% endblock %}