Recent advances in genomic interval analysis

# Recent advances in genomic interval analysis

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:25%">Augmented Interval Lists</div>
<div class="previewblock" style="width:25%"></div>
<div class="previewblock" style="width:40%">Regionset2vec</div>
<div class="previewblock" style="width:10%"></div>

<br clear="all">
<div class="previewblock" style="width:25%"></div>
<div class="previewblock" style="width:25%">Integrated Genome Database</div>
<div class="previewblock" style="width:40%"></div>
<div class="previewblock" style="width:10%">BEDbase</div>

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

# 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>
---

## Integrated Genome Database (IGD)

A high-performance search engine
for large-scale genomic interval datasets.

<div class="small">
<a href="https://github.com/databio/IGD">https://github.com/databio/IGD</a>
</div>

<span class="small bullet"><img src="/_modules/igd/icons/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1093/bioinformatics/btaa1062">Feng et al. (2021). <i>Bioinformatics</i>.</a></span>

<div style="padding:12px; font-size: 16pt; display:inline-block;">
<span style="border: 0px solid grey; float:right; margin: 0px 4px; padding: 0px 4px">
<img src="/_modules/igd/Feng.jpg" width="100" style="margin:0px;">
<br>Jianglin Feng
</span>
</div>

---

## Expanding the search space

<img src="/_modules/igd/subject-query-one-vs-many.svg">

---

## An integrated data structure

<img src="/_modules/igd/subject-query-one-vs-many-integrate.svg">

---

## GIGGLE

GIGGLE indexes many interval sets with a B+ tree.

<span class="small bullet"><img src="/_modules/igd/icons/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1038/nmeth.4556">Layer et al. (2018). <i>Nature Methods</i>.</a></span>

---

## IGD uses linear binning

- The genome is divided into equal-size bins
- Database intervals are placed in any bins they overlap
- Intervals are sorted by start coordinate within a bin

<img src="/_modules/igd/igd/igd_database.svg" height="400" style="background: white">

---

## Advantages

- Single-layer data structure has less overhead
- Bins are independent

## Challenges

- Duplication = bigger database
- Duplication = possible for double-counting

---

## Challenge 1: Database size

- Adjustable with bin size
- In practice: 5-20% bigger than raw, unduplicated data
- Can be 2x or more if you have smaller bins than regions
- Default bin size: 16,384 (2<sup>14</sup>)

---

## Challenge 2: Double-counting

Occurs only when both query and subject interval cross the same
bin boundary.

**Rule:** If the query crosses the left boundary of the bin, then any region in the bin that also crosses the left boundary will be skipped

<img src="/_modules/igd/igd/igd_database.svg" height="300" style="background: white">

---

## Question: Within a bin, how are overlaps calculated?

Can we use the AIList search algorithm?

Yes, but it doesn't help much because the bin size restricts the excess comparisons.

---

## Performance

---

## Conclusion

- IGD computes overlaps between a query and database of indexed interval sets
- IGD uses linear binning to index collections of region sets
- Because bins are independent, IGD uses little memory, and could be parallelized
- IGD reduces database size and increases performance
---

<div>
<h3>Region-set 2 Vec</h3>

Embeddings of genomic region sets <br> in lower dimensions.

<div class="small">
<a href="https://github.com/databio/regionset-embedding">https://github.com/databio/regionset-embedding</a><br>
</div>
</div>
<span class="small bullet"><img src="/_modules/regionset2vec/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1093/bioinformatics/btab439">Gharavi et al. (2021). <i>Bioinformatics</i>.</a></span>

---

### Word embeddings

<div class="small">http://suriyadeepan.github.io</div>

---

### Word2vec model

<img src="/_modules/regionset2vec/mikolov2013_fig1.png" width="680">
<br><span class="small bullet"><img src="/_modules/regionset2vec/paper.svg" height="25" class="bullet"><a href="https://arxiv.org/abs/1301.3781">Mikolov et al. (2013). <i>arXiv:1301.3781v3</i>.</a></span>

---

### Word context

<div class="well">
	You shall know a word by the company it keeps. (Firth 1957)<br>
	Words that occur in similar contexts tend to have similar meanings.
</div>
<div class="small">Image credit: Shubham Agarwal</div>

---

### Genomic context

<div class="well">
	A genomic interval is more likely to appear in a BED file with other genomic intervals of a similar function.
</div>

---

---

### Genomic Interval Embeddings

---

### Evaluation

We have created unsupervised 100-dimensional vector representations (embeddings) of region sets.<br>
Do relationships among vectors reflect biology?

---

## Evaluation 1: Classification performance

---

## Evaluation 1: Classification performance

---

### Evaluation 1: Classification performance

---

### Conclusion

<ul>
	<li>Regionset2vec adapts word2vec to learn genomic region embeddings</li>
	<li>Regionset2vec embeddings capture biological information</li>
	<li>NLP approaches can be adapted for applications in genomic interval analysis</li>
</ul>
---

iframe {
    width: 97% !important;
    height: 85% !important;
    -webkit-transform: scale(0.65);
    transform: scale(0.65);
    -webkit-transform-origin: 0 0;
    transform-origin: 0 0;
}
</style>

<div>
<h3>BEDbase</h3>

A high-performance server and API <br> for genomic interval data.

<br><span class="small bullet"><img src="/_modules/bedbase/web.svg" height="30" class="bullet"><a href="https://bedbase.org">bedbase.org</a></span>

</div>

---

<div>
<img src="/_modules/bedbase/bedbase_logo.svg" width="275">
<br>
A high-performance server and API <br> for genomic interval data.

<div class="small">
<a href="http://bedbase.org">http://bedbase.org</a><br>
</div>
</div>
<ul>
<li>Data spans projects (*e.g.* all data on GEO; 40,000 accessions, 100,000+ BED files)</li>
<li>Programmatic API for metadata, statistics, and data chunks</li>
<li>Human browsing of statistical and biological attributes</li>
<li>Aware of similarities among BED files</li>
<li>Human-friendly search</li>
<li>Shaped into 'non-redundant' sets for analysis</li>
</ul>

---

### BEDbase goals

- Human browsing of statistical and biological attributes
- Human-friendly, *intelligent* search
- Programmatic API for metadata, statistics, and data chunks
- Integrative analytical results
- Data spans projects (all data on GEO)

---

### BEDbase architecture

---

<br>BEDbase is a microservice for data interoperability,<br> not another cloud platform

---

<ol>
	<li style="color:yellow">Web interface (front-end)</li>
	<li style="">Clients (front-end)</li>
	<li style="">API (back-end)</li>
	<li style="">Database and files (back-end/infrastructure)</li>
	<li style="">Processing pipelines (infrastructure)</li>
	<li style="">Data served (content)</li>
</ol>

---

### Human browsing of BED file splash pages

<span class="small"><a href="https://bedbase.org/bed/bd2578e70c0efe3674d0d39c782fe9e1">https://bedbase.org/bed/bd2578e70c0efe3674d0d39c782fe9e1</a></span>
<div class="wrap">
<iframe src="https://bedbase.org/bed/bd2578e70c0efe3674d0d39c782fe9e1" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen ></iframe>
</div>

---

### Reference genome compatibility

---

### Reference genome compatibility

---

### Reference genome compatibility

---

### BEDsets allow comparison of BED files

<span class="small"><a href="https://bedbase.org/bedset/gse246900">https://bedbase.org/bedset/gse246900</a></span>
<div class="wrap">
<iframe src="https://bedbase.org/bedset/gse246900" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen ></iframe>
</div>

---

### Human-friendly search

<span class="small">Co-embedded metadata and region sets: <a href="https://bedbase.org/search?q=brain">https://bedbase.org/search?q=brain</a></span>

---

### Human-friendly search

---

### Human-friendly search

---

### Search by BED file

<span class="small">Co-embedded metadata and region sets: <a href="https://bedbase.org/search?view=b2b">https://bedbase.org/search?view=b2b</a></span>

---

<ol>
	<li style="">Web interface (front-end)</li>
	<li style="color:yellow">Clients (front-end)</li>
	<li style="">API (back-end)</li>
	<li style="">Database and files (back-end/infrastructure)</li>
	<li style="">Processing pipelines (infrastructure)</li>
	<li style="">Data served (content)</li>
</ol>

---

# BEDbase R client

---

```
library("bedbaser")
bedbase <- BEDbase(tempdir())
bb_to_granges(bedbase, "ab446df9a043222067863cfd536ee8e0")
```

```
GRanges object with 37 ranges and 5 metadata columns:
       seqnames            ranges strand |                   name     score
          [Rle]         [IRanges]  [Rle] |            [character] [integer]
   [1]    chr17 38083473-38083801      * | O-8A-H3K27ac_peak_11..        21
   [2]    chr17 38108871-38110066      * | O-8A-H3K27ac_peak_11..        25
   [3]    chr17 38137142-38137795      * | O-8A-H3K27ac_peak_11..        33
   [4]    chr17 38210828-38211063      * | O-8A-H3K27ac_peak_11..        17
   [5]    chr17 38218030-38220186      * | O-8A-H3K27ac_peak_11..        19
   ...      ...               ...    ... .                    ...       ...
  [33]    chr17 38603620-38604355      * | O-8A-H3K27ac_peak_11..        15
  [34]    chr17 38647047-38648053      * | O-8A-H3K27ac_peak_11..        28
  [35]    chr17 38708445-38710424      * | O-8A-H3K27ac_peak_11..        20
  [36]    chr17 38716283-38717201      * | O-8A-H3K27ac_peak_11..        23
  [37]    chr17 38803702-38804538      * | O-8A-H3K27ac_peak_11..        46
            field8      field9     field10
       [character] [character] [character]
   [1]     3.91024     4.82245     2.12195
   [2]     4.44410     5.31600     2.51785
   [3]     4.30183     6.25865     3.33754
   [4]     3.94862     4.34253     1.75554
   [5]     3.74929     4.57115     1.93712
   ...         ...         ...         ...
  [33]     3.80116     4.07741     1.55623
  [34]     4.35182     5.72967     2.89524
  [35]     3.88836     4.73101     2.06784
  [36]     4.24210     5.08399     2.33889
  [37]     5.09106     7.93609     4.68279
  -------
```

---

# BEDbase Python client

---

<ol>
	<li style="">Web interface (front-end)</li>
	<li style="">Clients (front-end)</li>
	<li style="color:yellow">API (back-end)</li>
	<li style="">Database and files (back-end/infrastructure)</li>
	<li style="">Processing pipelines (infrastructure)</li>
	<li style="">Data served (content)</li>
</ol>

---

## bedhost

A FastAPI application following JAMstack philosophy.<br>

<span class="fragment">JAMstack forces you to build a comprehensive API. </span>

---

### OpenAPI interface

<span class="small"><a href="https://api.bedbase.org/v1/docs">https://api.bedbase.org/v1/docs</a></span>
<div class="wrap">
<iframe src="https://api.bedbase.org/v1/docs" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen style="background: #FFFFFF;"></iframe>
</div>

---

### BED info via API

<span class="small"><a href="https://api.bedbase.org/v1/bed/bd2578e70c0efe3674d0d39c782fe9e1/metadata?full=true">https://api.bedbase.org/v1/bed/bd2578e70c0efe3674d0d39c782fe9e1/metadata?full=true</a></span>
<div class="wrap">
<iframe src="https://api.bedbase.org/v1/bed/bd2578e70c0efe3674d0d39c782fe9e1/metadata?full=true" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen style="background: #FFFFFF;"></iframe>
</div>

---

<ol>
	<li style="">Web interface (front-end)</li>
	<li style="">Clients (front-end)</li>
	<li style="">API (back-end)</li>
	<li style="color:yellow">Database and files (back-end/infrastructure)</li>
	<li style="">Processing pipelines (infrastructure)</li>
	<li style="">Data served (content)</li>
</ol>

---

## BEDbase data layer

1. BED file stored in Backblaze B2 (S3 compatible object store)
	- BED files n=21,438 (stats from 2025-05)
	- 346,071 total objects, 186.4 GB  ($6/TB/month)
2. B2 interface is routed through cloudflare CDN (free egress!)
3. File metadata stored in a PostgreSQL database on AWS managed Relational Database Service

## &rarr; Minimal maintenance cost

---

<ol>
	<li style="">Web interface (front-end)</li>
	<li style="">Clients (front-end)</li>
	<li style="">API (back-end)</li>
	<li style="">Database and files (back-end/infrastructure)</li>
	<li style="color:yellow">Processing pipelines (infrastructure)</li>
	<li style="">Data served (content)</li>
</ol>

---

- `bbconf`: bedbase configuration object, connection to database
- `bedqc`: a pipeline for QC of BED files.
- `bedmaker`: a pipeline to convert non-bed files into bed files
- `bedstat`: a pipeline to calculate stats for a bed file
- `bedbuncher`: a pipeline to create bedsets
- `bedembed`: a pipeline to create bed file embeddings

---

<img src="/_modules/genomicdistributions/genomic_distributions_dark.svg" width="275" style="padding-top:5px; padding-bottom:5px">
<div class="small">
Docs: <a href="http://code.databio.org/GenomicDistributions/">http://code.databio.org/GenomicDistributions/</a><br>
Code: <a href="http://github.com/databio/GenomicDistributions/">http://github.com/databio/GenomicDistributions/</a><br>
<div class="bullet">
<a href="https://bioconductor.org/packages/GenomicDistributions"><img src="/_modules/genomicdistributions/bioconductor_logo_grey.svg" height="22" style="padding-top:5px; padding-bottom:5px"> bioconductor.org/packages/GenomicDistributions</a><br>
</div>
</div>

<span class="small bullet"><img src="/_modules/genomicdistributions/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1186/s12864-022-08467-y">Kupkova et al. (2022).</a> <i>BMC Genomics</i>.</span><br/>

---

<img src="/_modules/genomicdistributions/genomicdistributions_summary.svg" width="100%">
---

<ol>
	<li style="">Web interface (front-end)</li>
	<li style="">Clients (front-end)</li>
	<li style="">API (back-end)</li>
	<li style="">Database and files (back-end/infrastructure)</li>
	<li style="">Processing pipelines (infrastructure)</li>
	<li style="color:yellow">Data served (content)</li>
</ol>

---

<div>
<img src="/_modules/geofetch/geofetch_logo.svg" width="275"><br>
Connects the Gene Expression Omnibus (GEO) <br>
and Sequence Read Archive (SRA) <br>
with PEP format<br>

</div>

<br><span class="small bullet"><img src="/_modules/geofetch/web.svg" height="25" class="bullet"><a href="https://geofetch.databio.org">geofetch.databio.org</a></span>
---

```
geofetch --filter="bed|bigBed|narrowPeak|broadPeak"
```

---

### Conclusion

<ul>
	<li>BEDbase provides BED data for humans and machines</li>
	<li>Output includes statistical and biological visualization</li>
	<li>Upcoming human-friendly search is powerful</li>
	<li>Programmatic access to data chunks improve interoperability</li>
</ul>
---

## Thank You

<b>Collaborators</b>
<br>Aakrosh Ratan
<br>Aidong Zhang
<br>Guangtao Zheng
<br>Don Brown
<br>Hyun Jae Cho
<br>Vince Carey
<br>Mikhail Dozmorov

<br><br>
<b>Alumni</b>
<br>Aaron Gu
<br>Jianglin Feng
<br>Ognen Duzlevski
<br>Tessa Danehy
</div>

<b>Sheffield lab</b>
<br>Erfaneh Gharavi
<br>Michal Stolarczyk
<br>John Lawson
<br>Jason Smith
<br>Kristyna Kupkova
<br>John Stubbs
<br>Bingjie Xue
<br>Jose Verdezoto
<br>Nathan LeRoy
<br>Oleksandr Khoroshevskyi
</div>

<div class="col3" style="font-size:.6em">
<b>Funding:</b><br>
<br><img src="/slides/genomic-intervals/logo/University_of_Virginia_Rotunda_logo.svg" height="40"><img src="/slides/genomic-intervals/logo/University_of_Virginia_logo_white.svg" height="40">
<br><img src="/slides/genomic-intervals/logo/NIH_logo_black.svg" height="80"><br>NIGMS R35-GM128636
</div>

<br clear="all"/>
<span class="small bullet"><a href="http://github.com/nsheff">nsheff</a></span> &middot;
<span class="small bullet"><a href="http://databio.org">databio.org</a></span> &middot;
<span class="small bullet"><a href="mailto:nsheffield@virginia.edu">nsheffield@virginia.edu</a></span><br>

</section>