Computational methods for region-based analysis of epigenome signals

# Computational methods for region-based analysis of epigenome signals

Nathan Sheffield

<span style="font-size:0.6em"><a href="http://www.databio.org/slides">www.databio.org/slides</a></span>

</section>
---

### Outline

<div class="previewblock" style="width:20%">The (epi)genome revolution</div>
<div class="previewblock" style="width:40%">Project organization</div>
<div class="previewblock" style="width:40%">Epigenome tools</div>

<div class="questionblock" style="background:#222; color:#eee; font-size: 0.6em; margin-top: 35px">&#9665; Questions &#9655;</div>
---

## Outline

**The (epi)genome revolution** (20%)
**Project organization** (40%)
**Epigenome tools** (40%)

---

## The genome revolution

---

A revolution driven by DNA sequencing technology

---

Sequencing technology can also measure epigenome signals

Epigenomics is the study of the chemical modification and physical conformation of cellular DNA and bound proteins

</div>

---

Rosa et al. 2013

</div>
<div class="col2">

- Histone modification: ChIP-seq 
- DNA methylation: Bisulfite-seq 
- Chromatin accessibility: ATAC-seq

</div>

---

---

### The Sequence Read Archive is growing

https://www.ncbi.nlm.nih.gov/sra/docs/sragrowth/

---

<div class="small">
<a href="{{project_url}}">{{project_url}}</a><br>
</div>
<span class="small bullet"><img src="/_modules/project-cover/icons/paper.svg" height="25" class="bullet" style="vertical-align: text-bottom; margin-right: 5px;">{{project_citations}}</span>
---

## Data is becoming more...

<div style="display: flex; justify-content: space-between;">
<div style="width: 30%; text-align: center;">
abundant
<img src="/_modules/pep/sequencing_costs_2015.jpg" width="100%">
</div>
<div style="width: 30%; text-align: center;">
available
<img src="/_modules/pep/cos_black.jpg" width="100%">
</div>
<div style="width: 30%; text-align: center;">
powerful
<img src="/_modules/pep/gwasw.jpg" width="100%">
</div>
</div>

---

## So why are the world's problems not solved?

---

---

## First step in bioinformatics analysis

<div style="display: flex; justify-content: space-between;">
<div style="width: 45%; text-align: center;">
<img src="/_modules/pep/icons/pipeline.svg" width="200">
pipeline
</div>
<div class="fragment" style="width: 45%; text-align: center;">
<img src="/_modules/pep/search_trends.svg" width="100%">
Papers with "bioinformatics pipeline" in title
</div>
</div>

---

## Problem solved?

---

## Problem solved?

---

## Problem solved?

---

## Data munging

---

## Then, downstream tools need a different organization

---

## What if?

---

## The solution

---

## The solution

---

## PEP: A standard format for project metadata

---

## PEP Ecosystem

---

## <img src="/_modules/pep/pep_logo.svg" width="70" style="vertical-align: middle;"> PEP format

<span class="bullet"><img src="/_modules/pep/icons/file.svg" width="30" class="bullet"> project_config.yaml</span>

```yaml
metadata:
  sample_annotation: /path/to/samples.csv
  output_dir: /path/to/output/folder
```

---

<span class="bullet"><img src="/_modules/pep/icons/file.svg" width="30" class="bullet"> samples.csv</span>

```csv
sample_name, protocol, organism, data_source
frog_0h, RNA-seq, frog, /path/to/frog0.gz
frog_1h, RNA-seq, frog, /path/to/frog1.gz
frog_2h, RNA-seq, frog, /path/to/frog2.gz
frog_3h, RNA-seq, frog, /path/to/frog3.gz
```
---

#### Microwave syndrome

<div class="well fragment">In user interface design, prioritizing easy access to integrated functions over their individual components. </div>

---

---

---

---

### The UNIX philosophy

<div class="col2">
<img src="/_modules/microwave-syndrome/unix_book.jpg" height="450">
</div>
<div class="col2">
<div class="well"><span style="color:#ffb; font-weight:bold">[T]he power of a system comes more from the relationships among programs than from the programs themselves.</span><br><br>
<span style="font-size: 0.8em">Many UNIX programs do quite trivial tasks in isolation, but, combined with other programs, become general and useful tools.</span><br/><br/>
<span class="small">- Kernighan and Pike, The UNIX Programming Environment (1983, p. viii)</span>
</div>
</div>

---

---

---

---

---

---

---

---

### Problem

### Solution

<img src="/_modules/microwave-syndrome/pep/data_input_plug.svg" width="375">
</div>
---

### Problem

</div>
<div class="col2">

### Solution

</div>

---

## PEP: Portable Encapsulated Projects

---

<div class="bullet">
  <h2><img src="/_modules/pep-format/pep_logo.svg" width="70">PEP format</h2>
</div>

Start with a simple CSV with tabular data.

<hr>
<div class="bullet">
<img src="/_modules/pep-format/file.svg" width="30">samples.csv
</div>

```
sample_name,protocol,organism,input_file
frog_0h,RNA-seq,frog,/path/to/frog0.gz
frog_1h,RNA-seq,frog,/path/to/frog1.gz
frog_2h,RNA-seq,frog,/path/to/frog2.gz
frog_3h,RNA-seq,frog,/path/to/frog3.gz
```

---

<div class="bullet">
	<h2><img src="/_modules/pep-format/pep_logo.svg" width="70">PEP format</h2>
</div>

Add a YAML for project-level data.

<hr>
<div class="bullet">
<img src="/_modules/pep-format/file.svg" width="30">samples.csv
</div>

<hr>
<div class="bullet">
<img src="/_modules/pep-format/file.svg" width="30">project_config.yaml
</div>

```yaml
sample_table: /path/to/samples.csv
output_dir: /path/to/output/folder
other_variable: value
```

---

### Add programmatic sample and project modifiers.

<div style="text-align: left">
<span class="bullet"><img src="/_modules/pep-format/replace_white.svg" width="50" class="bullet">Derived attributes</span><br>
<span class="bullet"><img src="/_modules/pep-format/implies_white.svg" width="50" class="bullet">Implied attributes</span><br>
<span class="bullet"><img src="/_modules/pep-format/subproject_white.svg" width="50" class="bullet">Subprojects</span><br>
</div>

---

<span class="bullet"><img src="/_modules/pep-format/replace_white.svg" width="50" class="bullet">Derived attributes</span><br>
<div class="well">Automatically build new sample attributes from existing attributes.</div>

Without derived attribute:

| sample_name | t | protocol | organism | input_file |
|-------------|---|:--------:|----------|------------|
| frog_0h | 0 | RNA-seq | frog | /path/to/frog0.gz |
| frog_1h | 1 | RNA-seq | frog | /path/to/frog1.gz |
| frog_2h | 2 | RNA-seq | frog | /path/to/frog2.gz |
| frog_3h | 3 | RNA-seq | frog | /path/to/frog3.gz |

Using derived attribute:

| sample_name | t | protocol | organism | input_file |
|-------------|---|:--------:|----------|------------|
| frog_0h | 0 | RNA-seq | frog | my_samples |
| frog_1h | 1 | RNA-seq | frog | my_samples |
| frog_2h | 2 | RNA-seq | frog | my_samples |
| frog_3h | 3 | RNA-seq | frog | my_samples |
| crab_0h | 0 | RNA-seq | crab | your_samples |
| crab_3h | 3 | RNA-seq | crab | your_samples |

---

Project config file:

```yaml
sample_modifiers:
  derive:
    attributes: [input_file]
    sources:
      my_samples: "/path/to/my/samples/{organism}_{t}h.gz"
      your_samples: "/path/to/your/samples/{organism}_{t}h.gz"
```

{variable} identifies sample annotation columns

<div class="well">Benefit: Enables distributed files, portability</div>

---

<span class="bullet"><img src="/_modules/pep-format/implies_white.svg" width="50" class="bullet">Implied attributes</span><br>

<div class="well">Add new sample attributes conditioned on values of existing attributes</div>

<div class="col2">
Before:<br>

| sample_name | protocol | organism |
|-------------|:--------:|----------|
| human_1 | RNA-seq | human |
| human_2 | RNA-seq | human |
| human_3 | RNA-seq | human |
| mouse_1 | RNA-seq | mouse |

</div>

<div class="col2">
After:<br>

| sample_name | protocol | organism | genome |
|-------------|:--------:|----------|--------|
| human_1 | RNA-seq | human | hg38 |
| human_2 | RNA-seq | human | hg38 |
| human_3 | RNA-seq | human | hg38 |
| mouse_1 | RNA-seq | mouse | mm10 |

</div>

---

| sample_name | protocol | organism |
|-------------|:--------:|----------|
| human_1 | RNA-seq | human |
| human_2 | RNA-seq | human |
| human_3 | RNA-seq | human |
| mouse_1 | RNA-seq | mouse |

Project config file:

```yaml
sample_modifiers:
  imply:
    - if: 
        organism: human
      then:
        genome: hg38
    - if:
        organism: mouse
      then:
        genome: mm10
```

<div class="well">Benefit: Divides project from sample metadata</div>

---

<span class="bullet"><img src="/_modules/pep-format/subproject.svg" width="50" class="bullet">Subprojects</span><br>

<div class="well">Define activatable project attributes.</div>

```yaml
project_modifiers:
  amendments:
    diverse:
      metadata:
        sample_annotation: psa_rrbs_diverse.csv
    cancer:
      metadata:
        sample_annotation: psa_rrbs_intracancer.csv
```

<div class="well">Benefit: Defines multiple similar projects in a single file</div>
---

---

### Locus Overlap Analysis

<div class="small">
<a href="http://code.databio.org/LOLA/">http://code.databio.org/LOLA/</a><br>
</div>
<span class="small bullet"><img src="/_modules/lola-intro/paper.svg" height="25" class="bullet">Sheffield and Bock (2016). <i>Bioinformatics</i>.</span><br/>
<span class="small bullet"><img src="/_modules/lola-intro/paper.svg" height="25" class="bullet">Nagraj, Magee, and Sheffield (2018). <i>Nucleic Acids Research</i>.</span>
---

<div class="small">
<a href="http://code.databio.org/LOLA/">http://code.databio.org/LOLA/</a><br>
</div>

<span style="font-size: 0.8em;"><img src="/shorts/lola/paper.svg" height="25" style="vertical-align: text-bottom; margin-right: 5px;">Sheffield and Bock (2016). *Bioinformatics*.</span><br/>
<span style="font-size: 0.8em;"><img src="/shorts/lola/paper.svg" height="25" style="vertical-align: text-bottom; margin-right: 5px;">Nagraj, Magee, and Sheffield (2018). *Nucleic Acids Research*.</span>

---

![New data](/shorts/lola/01-new-data.svg)

---

![New data connection](/shorts/lola/02-new-data-connection.svg)

---

![GSEA](/shorts/lola/03-gsea.svg)

---

![HTS](/shorts/lola/04-hts.svg)

---

![Convert](/shorts/lola/05-convert.svg)

---

![Introducing LOLA](/shorts/lola/06-introducing-lola.svg)

---

![LOLA 1](/shorts/lola/07-lola1.svg)

---

![LOLA 2](/shorts/lola/08-lola2.svg)

---

![Test](/shorts/lola/09-test.svg)

---

![Results](/shorts/lola/10-results.svg)

---

![EWS vs others 2](/shorts/lola/ews_vs_others2.svg)

---

![EWS vs others 3](/shorts/lola/ews_vs_others3.svg)

---

## LOLAweb

A shiny app and server for interactive LOLA analysis.

Public server: [http://lolaweb.databio.org](http://lolaweb.databio.org)

GitHub: [https://github.com/databio/LOLAweb](https://github.com/databio/LOLAweb)

---

### DEMO

<video controls width="800">
  <source src="lw.webm" type="video/webm">
Your browser does not support the video tag.
</video>
---

# LOLA refresher

![LOLA abstract](/shorts/ailist/lola-abstract.svg)

---

# LOLA requires comparing sets of intervals

![Subject query](/shorts/ailist/subject-query.svg)

Can we improve the efficiency to enable faster, larger-scale analysis?

---

# If subject list has no containment, identifying overlaps is fast

![Subject query annotated](/shorts/ailist/subject-query-annotated.svg)

binary search on start intervals, followed by backward steps:

![Binary search](/shorts/ailist/binary-search.svg)

---

# The problem arises with contained interval overlaps

![Subject query containment](/shorts/ailist/subject-query-containment.svg)

![Binary search fail](/shorts/ailist/binary-search-fail.svg)

---

# How can we improve efficiency without guaranteeing no containment?

---

# Many approaches to solve the 'containment' issue:

- Nested Containment Lists (GRanges) (Alekseyenko and Lee, 2007; Aboyoun, P, Pages, H, and Lawrence, 2012)
- R-trees (bedtools) (Kent et al., 2002; Quinlan and Hall, 2010), Augmented interval trees (Cormen et al., 2001)

These methods try to structure the data to provide non-containment guarantees

---

# Methods provide non-containment guarantees

### R-trees

Annotates tree nodes with a *minimum bounding rectangle* of elements. A query that does not intersect the bounding rectangle will not intersect any child element.

</div>

### Nested Containment Lists

![NCList](/shorts/ailist/nclist.png)

</div>

---

# Augmented Interval List

1. Augment the list with the running maximum *end* value. *solves the problem for lowly-contained lists*

2. Decompose the list to minimize containment. *extends the solution to highly-contained lists*

---

# Augment with the running maximum end value, `maxE`

Provides a *local guarantee* of no containment.

![AIList maxE](/shorts/ailist/ailist-maxE.svg)

---

# AIList works on contained lists

![Subject query containment](/shorts/ailist/subject-query-containment.svg)

![Binary search maxE](/shorts/ailist/binary-search-maxE.svg)

---

# But long containment runs are problematic

![Subject query containment2](/shorts/ailist/subject-query-containment2.svg)

![Binary search maxE2](/shorts/ailist/binary-search-maxE2.svg)

---

# Decompose long runs with constant `maxE`

![AIList decompose](/shorts/ailist/ailist-decompose.svg)

---

# Performance

- How does the `maxE` minimum run length affect performance?
- How does it compare to existing approaches?
- How does it scale with increasing size of subject?

---

# Datasets

![Table 1](/shorts/ailist/ailist_table1.svg)

---

# How does the `maxE` minimum run length affect performance?

![Figure 2](/shorts/ailist/ailist_fig2.svg)

---

# How does it compare to existing approaches?

![Figure 3](/shorts/ailist/ailist_fig3.svg)

---

# How does it scale with increasing size of subject?

![Figure 4](/shorts/ailist/ailist_fig4.svg)

---

# Conclusion and Directions

AIList is best-in-class for one-to-one interval comparisons

---

## Acknowledgments

**Sheffield lab**
- John Lawson
- Vince Reuter
- Ognen Duzlevski
- Jason Smith
- **Jianglin Feng**
- Michal Stolarczyk
- Aaron Gu
- Anant Tewari

</div>

**Funding:**

</div>

</div>
---

## Conclusion

Pepkit provides a start-to-finish toolkit for processing epigenome data.

[pepkit.github.io](http://pepkit.github.io)

</div>
</div>
<div class="col2">
<div style="padding:7px">

LOLA is one of our tools to ask biological questions of genomic regions

[code.databio.org/LOLA](http://code.databio.org/LOLA)

</div>
</div>

---

## Acknowledgments

**Sheffield lab**
- John Lawson
- Vince Reuter
- Jason Smith
- Jianglin Feng
- Michal Stolarczyk
- Aaron Gu
- Ognen Duzlevski

</div>

**SOM research computing**
- Pete Nagraj
- Neal Magee

</div>
<div class="col3" style="font-size:.6em">

**Funding:**

</div>

---

# Thank You

<span class="small bullet"><img src="/images/external/github_bug_black.svg" height="20" class="bullet"><a href="http://github.com/nsheff">nsheff</a></span> &middot;
<span class="small bullet"><img src="/images/icons/web.svg" height="25" class="bullet"><a href="http://databio.org">databio.org</a></span> &middot;
<span class="small bullet"><img src="/images/icons/letter.svg" height="25" class="bullet"><a href="mailto:nsheffield@virginia.edu">nsheffield@virginia.edu</a></span>

</section>