# Efficient memory representation of sequences with few mutations

**URL:** <https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466>\
**Category:** Biology, Health, and Medicine\
**Tags:** question\
**Created:** [April 24, 2019, 10:08am UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466 "2019-04-24T10:08:56Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 24, 2019, 10:08am UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/1 "2019-04-24T10:08:56Z")

</div>

I have a dataset which consists of a wild-type sequence and many (\sim10^7 or more) mutated sequences which differ from the wild-type in only a few positions. I want to represent this efficiently in memory, by storing the wild-type sequence only once and then storing only the mutations of each mutated sequence.

Does `BioSequences` offer some facility for this kind of representation?  
Otherwise, any advice on how I might approach this?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 24, 2019, 11:19am UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/2 "2019-04-24T11:19:46Z")

</div>

> [@e3c6](#):
>
> Otherwise, any advice on how I might approach this?

A wrapper `<: AbstractVector` type that stores the indexes and values for the differences, and has a `Base.getindex` that looks up if the index is in the changed set or not, and returns the value accordingly.

The best representation depends on details, eg a sorted vector, or a `Dict` of indexes.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 24, 2019, 11:47am UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/3 "2019-04-24T11:47:27Z")

</div>

I thought of something like this.

```julia
Change = NamedTuple{(:pos,:x), Tuple{Int,Int}}
struct DiffSeq{L,D}
	s0::NTuple{L,Int}
	dif::NTuple{D, Change}
end

```

And then defined the iterator interface accordingly.  
Here `s0` is the wild-type sequence, and it is shared across may `DiffSeq` instances. However this only makes sense if `s0` is only allocated in memory once.

The documentation says that `(...) in some cases the compiler is able to avoid allocating immutable objects entirely.` In this case `s0` is an `NTuple` which is immutable. But how can I be sure it is not being allocated many times?

---

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [April 24, 2019, 1:55pm UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/4 "2019-04-24T13:55:54Z")

</div>

> [@e3c6](#):
>
> The documentation says that `(...) in some cases the compiler is able to avoid allocating immutable objects entirely.` In this case `s0` is an `NTuple` which is immutable. But how can I be sure it is not being allocated many times?

I don’t think you can. Immutable types in Julia are defined by their value, and not by their memory address as mutable types are. If s0 was a vector and not a tuple, then that s0 vector is passed by reference (defined by it’s memory address), and so if you pass a vector to many DiffSeqs as their s0, you know all those DiffSeqs will share that very same vector. Which you can’t know AFAIK if you use a NTuple.

---

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [April 24, 2019, 1:59pm UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/5 "2019-04-24T13:59:51Z")

</div>

You could also check out BioAlignments.jl, which has a datastruture which represents one sequence (an aligned sequence) as a reference to some reference sequence, and a set of edit operations (match, mismatch, indel and so on).

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 24, 2019, 2:02pm UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/6 "2019-04-24T14:02:46Z")

</div>

> [@Ward9250](#):
>
> check out BioAlignments.jl

I think this is just what I was looking for! Thanks.

**Edit:** On second thought, I don’t see how this helps me. It doesn’t seem to be able to convert the `AlignedSequence` to a `Sequence`. In that case I might as well just use the `struct` I created above.

---

<div class="post-metadata">

**Author:** ![bicycle1885](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bicycle1885/32/107_2.png) [@bicycle1885](https://discourse.julialang.org/u/bicycle1885)\
**Post date:** [April 24, 2019, 2:19pm UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/7 "2019-04-24T14:19:20Z")

</div>

I think the best data structure highly depends on the operations you want to perform. `AlignedSequence` would be possible to represent such mutated sequences, but it is not clear whether it meets your needs because we don’t know what you really want to do on them.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 24, 2019, 2:24pm UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/8 "2019-04-24T14:24:40Z")

</div>

I usually just trust the compiler on this, its heuristics are quite good.

I am not sure `NTuple` is a good type for a long sequence though. Just use a vector. Or leave it as a type parameter so it works with any kind of `<:AbstractVector`.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 24, 2019, 2:27pm UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/9 "2019-04-24T14:27:17Z")

</div>

> [@bicycle1885](#):
>
> I think the best data structure highly depends on the operations you want to perform. `AlignedSequence` would be possible to represent such mutated sequences, but it is not clear whether it meets your needs because we don’t know what you really want to do on them.

I want to be able to access the sequence letters via `getindex`, but especially iterate through them as fast as possible.

---

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [May 1, 2019, 11:04am UTC](https://discourse.julialang.org/t/efficient-memory-representation-of-sequences-with-few-mutations/23466/10 "2019-05-01T11:04:14Z")

</div>

You should be able to convert between the two, by iterating over every element of the aligned sequence and use that to build a new sequence. Something like `DNASequence(collect(my_aligned_sequence))`