BioJulia/Bio.jl — pull request #15 by dcjones (2014-07-12 17:01:17+00:00)
Title: WIP: Sequences

I'm starting in on sequences. I laid out the basic design I had in mind in #6. I'll document my progress, and any changes to that design as I add commits to this PR.

Progress so far: I have a `NucleotideSequence` type (and specializations `DNASequence` and `RNASequence` that uses 2-bit encoding).

One major decision I've made since starting work is that sequence types should be immutable. Immutable sequence types allow for cheap subsequences, since you don't have to copy the actual sequence, just specify a range, as long as you can assume the data won't change. It is a tradeoff, but cheap subsequences would allow, for example, extracting the sequence of every exon in the human genome extremely efficiently.

I've already implemented the cheap subsequence idea, so you can do:
```julia
x = dna"ACCCATGATANNNTAGATTTTATAGATAT"
y = x[5:10]
```
No copying of the underlying sequence is performed and `typeof(x) == typeof(y) == DNASequence`, so subsequences are first-class citizens, and indistinguishable from sequences.

What I'm struggling with now: my initial idea was to indicate Ns in the sequence using an IntervalTree. I'm worried now that the efficiency of that implementation depends too much on the assumption that Ns are rare and occur in large blocks. Sequence construction is now unacceptably slow if I use random sequences with `N` occurring with 0.2 probability. Constructing 1e6nt sequence from a string takes 0.01 seconds without `N` and 0.38 seconds with N in these perverse random sequences.

I'm thinking now of an alternate data structure I can use, maybe something based on run-length encoding.