{"action":"created","issue":{"url":"https://api.github.com/repos/BioJulia/Bio.jl/issues/122","labels_url":"https://api.github.com/repos/BioJulia/Bio.jl/issues/122/labels{/name}","comments_url":"https://api.github.com/repos/BioJulia/Bio.jl/issues/122/comments","events_url":"https://api.github.com/repos/BioJulia/Bio.jl/issues/122/events","html_url":"https://github.com/BioJulia/Bio.jl/issues/122","id":116699948,"number":122,"title":"[RFC] More nucleotides","user":{"login":"bicycle1885","id":905683,"avatar_url":"https://avatars.githubusercontent.com/u/905683?v=3","gravatar_id":"","url":"https://api.github.com/users/bicycle1885","html_url":"https://github.com/bicycle1885","followers_url":"https://api.github.com/users/bicycle1885/followers","following_url":"https://api.github.com/users/bicycle1885/following{/other_user}","gists_url":"https://api.github.com/users/bicycle1885/gists{/gist_id}","starred_url":"https://api.github.com/users/bicycle1885/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bicycle1885/subscriptions","organizations_url":"https://api.github.com/users/bicycle1885/orgs","repos_url":"https://api.github.com/users/bicycle1885/repos","events_url":"https://api.github.com/users/bicycle1885/events{/privacy}","received_events_url":"https://api.github.com/users/bicycle1885/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/BioJulia/Bio.jl/labels/RFC","name":"RFC","color":"fbca04"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":13,"created_at":"2015-11-13T04:56:01Z","updated_at":"2015-11-16T07:26:12Z","closed_at":null,"body":"I'd like to share and discuss ideas about DNA or RNA sequences, partially mentioned in #55.\r\n\r\nCurrently, only five nucleotides (A/C/G/T/N) are defined in this package and a DNA sequence cannot store other ambiguous nucleotides like M (A or C). This is because we use 2-bit encoding for A/C/G/T and 1-bit ambiguity mask for N. This limitation will definitely cause problems in real-world bioinformatics. Since we are creating a general purpose infrastructure for bioinformatics, this would be an intolerable limitation.\r\n\r\nI think we should, at least, support all nucleotide base codes defined by IUPAC, which includes all possible combinations of four nucleotides (http://www.ncbi.nlm.nih.gov/Class/MLACourse/Modules/MolBioReview/iupac_nt_abbreviations.html).\r\nIf we use 4-bit encoding, we can store any nucleotides listed here. These ambiguous nucleotides are, of course, allowed in the Biostrings package of Bioconductor. An apparent drawback of 4-bit encoding is that it requires more space than the current (2+1)-bit encoding: the data size of a DNA sequence will become 4/3 = 1.333 times larger. But I think this will not be a serious problem in most cases because it is very rare to handle such a large sequence that hits the RAM limit except eukaryotic reference sequences. For such long sequences, we can prepare a reference sequence type that adopts 2-bit encoding for A/C/G/T + compressed N mask, which is already implemented in my FMM.jl package (https://github.com/bicycle1885/FMM.jl/blob/master/src/genomicseq.jl).\r\n\r\nOne advantage of this 4-bit encoding is that it will improve the performance of random access on DNA sequences. This is because the current implementation stores the N mask in a separated bit vector object, and hence it has a branch (`if seq.ns[i]) ... else ... end`) to access an element in a sequence:\r\n\r\n```julia\r\nfunction getindex{T}(seq::NucleotideSequence{T}, i::Integer)\r\n    if i > length(seq) || i < 1\r\n        throw(BoundsError())\r\n    end\r\n    i += seq.part.start - 1\r\n    if seq.ns[i]\r\n        return nnucleotide(T)\r\n    else\r\n        return getnuc(T, seq.data, i)\r\n    end\r\n```\r\n\r\nBut using 4-bit encoding, we can store all information in a vector so that any branch is not need any more. That would lead to a significant performance improvement in intensive-sequence-access algorithms like pairwise alignment."},"comment":{"url":"https://api.github.com/repos/BioJulia/Bio.jl/issues/comments/156945632","html_url":"https://github.com/BioJulia/Bio.jl/issues/122#issuecomment-156945632","issue_url":"https://api.github.com/repos/BioJulia/Bio.jl/issues/122","id":156945632,"user":{"login":"bicycle1885","id":905683,"avatar_url":"https://avatars.githubusercontent.com/u/905683?v=3","gravatar_id":"","url":"https://api.github.com/users/bicycle1885","html_url":"https://github.com/bicycle1885","followers_url":"https://api.github.com/users/bicycle1885/followers","following_url":"https://api.github.com/users/bicycle1885/following{/other_user}","gists_url":"https://api.github.com/users/bicycle1885/gists{/gist_id}","starred_url":"https://api.github.com/users/bicycle1885/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bicycle1885/subscriptions","organizations_url":"https://api.github.com/users/bicycle1885/orgs","repos_url":"https://api.github.com/users/bicycle1885/repos","events_url":"https://api.github.com/users/bicycle1885/events{/privacy}","received_events_url":"https://api.github.com/users/bicycle1885/received_events","type":"User","site_admin":false},"created_at":"2015-11-16T07:26:12Z","updated_at":"2015-11-16T07:26:12Z","body":"@Ward9250 You are right. In fact, I've found NMask can be thought as a indexable bit vector, so I may add this data structure to the IndexableBitVectors.jl package. I think someone already invented the same idea, and if so, I'd like to use the name."}}