1 of 19

Project 2: Inference of chromatin looping status from live cell imaging data

Hongyu Yu, Shreya Mishra, Tee Udomlumleart, Sion Kim, Paul Meneses

3 of 19

Chromatin loops are formed by cohesins

Shi et al., 2020 and Cees Dekker

Robust developmental processes and proper cellular homeostasis depends on enhancer and promoter interactions.
Multi-subunit motor protein called cohesins can reel in DNA, bringing distal promoters and enhancers closer together and forming chromatin loops.
Main questions:

When are an enhancer and its cognate promoter in the same chromatin loop?
What is the distance of their interaction? How long? And how often?

Cohesin structure

Loop extrusion animated cartoon

4 of 19

Study chromatin behavior through live-cell imaging

Current live-cell imaging experiments can track the movement of DNA over time.

We can leverage this technique to study EP kinetics.

�

5 of 19

Imaging chromatin traces in real time is challenging

Gabriele et al., 2022

Experimental limitations allow simultaneous tracking of only upto 2-3 genomic loci over time.
This limitation in imaging necessitates computational methods to infer cohesin looping status on the genome.

Currently, there are two methods…

BILD (Bayesian Inference of Looping Dynamics) by Gabriele, …, Anders Hansen
HMM (Hidden Markov Model) by Mach, …, Luca Giorgetti

6 of 19

Comparison between BILD and HMM looping inference algorithms

	Mach et al (HMM)	Gabriele et al (BILD)
Method	Two-state HMM with all parameters being unknown (transition probabilities, Gaussian means and variances)	Determine biophysical constants (BayesMSD) Express likelihood based on Rouse model Bayesian inference
Advantages	Easy to run, with examples Simple model	Inference is based on biophysical/polymer parameters that best explain the dynamics between two spots
Disadvantages	HMM fails to run when trajectories have missing values Assumes the input distributions are Gaussian. Inputs used in the paper are not normally distributed.	Complicated, no examples provided We fail to implement BILD during this hackathon :( sadge

7 of 19

Current methods do not agree

Gabriele et al., 2022

Apply Mach et al’s HMM to Gabriele et al’s data

Fit on the wild type (C36, with both looped and unlooped states) to get HMM parameters
Apply the fitted model to other strains to make conclusions (loop fraction/frequency)

C65

8 of 19

Our projects: Overview

Focus on improving HMM algorithms by …

Imputing missing values before entering them into HMM.
Reformulate HMM to better model a gaussian process.
Rederive HMM to allow incorporation of NaN values.

Apply HMM to Gabriele et al’ data (1min)

Overall statistics: loop fraction, loop lifetime (if time permits)
Show some trajectories (plot both HMM and BILD)
BILD does not work -> we focus on improving HMM

1st improvement: imputation and smoothing (1min)

Describe imputation and smoothing methods, just plot a sample trajectory
Loop fractions: still high, ~60-70%, different from real data

2nd improvement: normal distribution & fix the covariance and mean (2min)

Normal distribution: show the plots of distances and axis differences
Covariance: plot difference -> show different states have different variances -> incorporate this information into the model
Result: loop fraction/plot distance distributions/lifetime/sample trajectories, justify

Simulation is necessary and natural

3rd improvement: modify hmmlearn to allow incomplete input (1min)

Result: same as above

9 of 19

Imputation algorithms

HMM_ffill
kalman_StructTS (using structural model fitted by maximum likelihood)
kalman_auto_arima (using state space representation of arima model)
weighted_rolling_avg (Rolling window : 4)
simple_rolling_avg (Rolling window : 4)
interpolation_linear
interpolation_stine

HMM_fill: fill missing data points using last previous datapoint in the series.

kalman_StructTS: Utilizes a structural model fitted by maximum likelihood.

kalman_auto_arima: Relies on the state space representation of an ARIMA model.

weighted_rolling_avg: Computes a rolling average with a window size of 4, using weighted values.

simple_rolling_avg: Calculates a rolling average with a window size of 4, using equal weights.

interpolation_linear: Performs linear interpolation to estimate missing data points.

interpolation_stine: Utilizes Stineman interpolation for data imputation. (Assumes : If values of the ordinates of the specified points change monotonically, and the slopes of the line segments joining the points change monotonically, then the interpolating curve and its slope will change monotonically.)

savgol_filter: Applies the Savitzky-Golay filter for smoothing noisy signals.

median_filter: Uses a median filter to reduce noise in time series data.

butter_filter: Implements a Butterworth filter for signal processing.

kalman_StructTS: Utilizes a structural model fitted by maximum likelihood.

kalman_auto_arima: Relies on the state space representation of an ARIMA model.

weighted_rolling_avg: Computes a rolling average with a window size of 4, using weighted values.

simple_rolling_avg: Calculates a rolling average with a window size of 4, using equal weights.

interpolation_linear: Performs linear interpolation to estimate missing data points.

interpolation_stine: Utilizes Stineman interpolation for data imputation.

savgol_filter: Applies the Savitzky-Golay filter for smoothing noisy signals.

median_filter: Uses a median filter to reduce noise in time series data.

butter_filter: Implements a Butterworth filter for signal processing.

Kalman_StructTS (Structural Time Series):

Idea: Imagine you’re tracking the height of a growing plant. The Kalman_StructTS model combines what you know about the plant’s growth trend (structural model) with the noisy measurements you take each day.

How It Works: It adjusts the estimated growth rate based on new measurements while considering uncertainties (like cloudy days affecting growth).

Application: Used in weather forecasting, stock market predictions, and even tracking COVID-19 cases.

Kalman_Auto_ARIMA (State Space Representation of ARIMA):

Idea: Think of a car driving on a winding road. The Kalman_Auto_ARIMA model represents the car’s changing speed (state) while considering road conditions (ARIMA components).

How It Works: It adapts to twists and turns, adjusting the speed to maintain a smooth ride.

Application: Used in self-driving cars, robotics, and financial modeling.

Weighted_Rolling_Avg (Rolling Window: 4):

Idea: Imagine you’re calculating your weekly allowance. The Weighted_Rolling_Avg gives more importance to recent spending (last 4 weeks) when estimating your overall budget.

How It Works: It smooths out spending fluctuations while considering recent trends.

Application: Used in financial planning and sales forecasting.

Simple_Rolling_Avg (Rolling Window: 4):

Idea: Picture a water tank filling up with a faucet. The Simple_Rolling_Avg calculates the average water level over the last 4 measurements.

How It Works: It evens out water level variations caused by sudden changes in flow.

Application: Used in water management and inventory tracking.

Interpolation_Linear:

Idea: Imagine drawing a straight line between two known points on a treasure map. Linear interpolation estimates where the hidden treasure might be along that line.

How It Works: It connects the dots smoothly, assuming a straight path.

Application: Used in GPS navigation and graphics rendering.

Interpolation_Stine:

Idea: Suppose you’re hiking in a forest with uneven terrain. Stineman interpolation adapts to the landscape—whether it’s a steep hill or a flat path—while estimating your position between known landmarks.

How It Works: It adjusts the path based on local features.

Application: Used in geospatial mapping and terrain modeling.

SavGol Filter:

Idea: Think of a bumpy road. The SavGol filter smooths out the road surface while driving, making the ride more comfortable.

How It Works: It adjusts the bumps (noise) without changing the overall route.

Application: Used in signal processing and scientific data analysis.

Median Filter:

Idea: Imagine a classroom where students randomly shout. The Median Filter identifies the most common volume level (median) to restore a quieter learning environment.

How It Works: It ignores extreme noise (shouting) and focuses on the typical level.

Application: Used in image denoising and sensor data cleaning.

Butterworth Filter:

Idea: Consider a music performance with background noise. The Butterworth filter acts like an adjustable audio equalizer, reducing the noise frequencies while keeping the main melody clear.

How It Works: It fine-tunes the sound to improve quality.

Application: Used in audio processing and electronic circuits.

10 of 19

Imputation results

11 of 19

Smoothing algorithm

(tested on HMM_base_filled)

scipy.signal.savgol_filter
Others: butter, median, etc.

CTCF 0hr Trace 55

distance

12 of 19

Developing HMM+

Motivations

Mach et al., 2022

HMM (Mach et al., 2022) modelled the euclidean distance between trajectories as a mixture of Gaussians for the looped and unlooped states.

Distribution appears to be skewed to the right
Gaussian implicitly assumes the support is all real values

13 of 19

Developing HMM+

Semi-supervised Multivariate Gaussian HMM

Mach et al., 2022

Idea:

Reformulate HMM to model each axis as an independent univariate Gaussian
Fix covariance matrix based on control data to help the model distinguish states

C36 (WT) ,C65 (no CTCF), RAD21 depleted

14 of 19

Developing HMM++

Directly fit HMM from hmmlearn on incomplete data

hmmlearn: Hidden Markov Models in Python with scikit-learn like API

https://pypi.org/project/hmmlearn/

hmmlearn does not allow input with NaN’s

Automatically raise errors if input contains NaN
Fitting: backward-forward algorithms failed

NaNs propagate to all values
Cannot calculate likelihood/probability

Decoding: viterbi algorithm failed

NaNs propagate to all values

Solution:

Rederive the EM algorithm with missing values
Change the source code of hmmlearn library

15 of 19

Results by applying modified HMM to Gabriele et al data

Predicted loop fraction

C65 Sample Trajectory

C36 Sample Trajectory

Mean loop lifetimes

	Control (C65)	Wildtype (C36)
Mach	54.2%	74.1%
HMM+ (filled)	13.3%	24.6%
BILD	4.7%	7%
HMM++	10.5%	20%

Here we present the results when applying these different models to Gabriele et al data.

For the loop fraction, the default hidden Markov model from Mach et al’s paper gave high loop fraction for both the control and the wild type. Indeed, the model predicts that the loop formed in more than 50% of the time even in the absence of CTCF sites. In contrast, by changing the distribution and fixing the covariance matrix, we lowered this proportion to 13%, and further modifying the EM algorithm results in even fewer false positives. The BILD method, on the other hand, reports the fewest loops in the control group, but it also gives much lower loop fraction for the wild type as well. We believe that is because BILD is too conservative.

Comparing the second and the last row, we see that modifying the EM is really helping avoid singletons and false positives.

16 of 19

Simulations enable benchmarking of current methods

Workflow

Grid search

MSD

…

MSD

Observed WT Trajectories

Mean MSD

(Optional)

Missingness

Simulator

similarity(

)

Choose maximum similarity for optimal simulation parameters

17 of 19

Simulations show HMM++ is robust to missing data

Looped
Unlooped
Missing

18 of 19

Summary and Future directions

Here we present current limitations in cohesin loop inference algorithms and offer several ways to improve them.

To benchmark model performance, it is crucial to have real ground truth

Simulations are only approximations of real data
Cohesin live imaging to see the true loop status

If no ground truth, come up with new rationale to evaluate models qualitatively�e.g. if a model predicts more loops on control than wild type, then probably not working or use molecular dynamics (MD) simulations.
Downstream analysis: interpret cell type/variability from looping dynamics

19 of 19

Acknowledgements

4DN Group: Predictive Modeling Working Group
Organizers: Akanksha Sachan, Anupama Jha, Katie Gjoni, Rui Yang, Sean Moran, Shu Zhang
Team 2: Project Managers: Hongyu Yu, Shreya Mishra

Participants: Tee Udomlumleart, Sion Kim, Paul Meneses

Mach. et., al. (HMM), Simon Grosse-Holz (BILD)
Daiqing Wu from Yun Li Lab at UNC-Chapel Hill