{"action":"created","issue":{"url":"https://api.github.com/repos/andy-thomason/genetics/issues/3","labels_url":"https://api.github.com/repos/andy-thomason/genetics/issues/3/labels{/name}","comments_url":"https://api.github.com/repos/andy-thomason/genetics/issues/3/comments","events_url":"https://api.github.com/repos/andy-thomason/genetics/issues/3/events","html_url":"https://github.com/andy-thomason/genetics/issues/3","id":105894828,"number":3,"title":"Suffix Arrays","user":{"login":"kloetzl","id":7765807,"avatar_url":"https://avatars.githubusercontent.com/u/7765807?v=3","gravatar_id":"","url":"https://api.github.com/users/kloetzl","html_url":"https://github.com/kloetzl","followers_url":"https://api.github.com/users/kloetzl/followers","following_url":"https://api.github.com/users/kloetzl/following{/other_user}","gists_url":"https://api.github.com/users/kloetzl/gists{/gist_id}","starred_url":"https://api.github.com/users/kloetzl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kloetzl/subscriptions","organizations_url":"https://api.github.com/users/kloetzl/orgs","repos_url":"https://api.github.com/users/kloetzl/repos","events_url":"https://api.github.com/users/kloetzl/events{/privacy}","received_events_url":"https://api.github.com/users/kloetzl/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-09-10T20:49:46Z","updated_at":"2015-09-11T13:05:41Z","closed_at":null,"body":"The section in the Readme on suffix arrays is flawed.\r\n\r\n> Most genetic searches revolve around the creation of Suffix Arrays which are a sort of all the substrings of a sequence to the end.\r\n\r\nYes, and no. Most use an *enhanced* suffix array.\r\n\r\n> \"hello\" consists of the substrings \"hello\", \"ello\", \"llo\", \"lo\", \"~~p~~o\" and \"\"\r\n> The suffix array is:\r\n> 5 \"\" 1 \"ello\" 0 \"hello\" 3 \"lo\" 2 \"llo\" 4 \"o\"\r\n\r\n\"llo\" < \"lo\"!\r\n\r\n> We can use the suffix array to look up the position of any sequence by, for example, doing a binary ~~chop~~ *search* on the *suffixes*. In practice this is not a sensible thing to do as each of the memory accesses to the *suffixes* may cost thousands of cycles.\r\n\r\nAccessing main memory should be a few hundred (like 200) cycles; not thousands.\r\n\r\n> Calculating a full suffix array for the 3.2 billion letters of the human genome is an expensive process, but fortunately we don't need to compute a full suffix array as sequences of 16 or more letters are *likely* to be unique.\r\n\r\n“Likely“ is the important word here. See this paper for the distribution of [match lengths](http://online.liebertpub.com/doi/abs/10.1089/cmb.2009.0106). Also, here is a recent paper, using your *uniqueness* idea to [create a SA](http://www.sciencedirect.com/science/article/pii/S1570866714000173).\r\n\r\n> Far better is to calculate a hybrid indexed suffix array which gives you all the substrings starting with a fixed number of letters. For this we add an index of 2^(2N) entries for N letters the suffixes sorted by address in the array instead of value.\r\n\r\nWhat is *far better* really depends on what one wants to do with the SA. Searching for substrings, MEMs, MUMs and computing matching statistics are completely different things! Some require the LCP array, or even RMQ (CLD).\r\n\r\nProbably one of the best C++ libraries for SAs is [SDSL-lite](https://github.com/simongog/sdsl-lite). Go, check it out.\r\n\r\nBest,\r\nFabian\r\n\r\nps. You should http://choosealicense.com/"},"comment":{"url":"https://api.github.com/repos/andy-thomason/genetics/issues/comments/139540568","html_url":"https://github.com/andy-thomason/genetics/issues/3#issuecomment-139540568","issue_url":"https://api.github.com/repos/andy-thomason/genetics/issues/3","id":139540568,"user":{"login":"kloetzl","id":7765807,"avatar_url":"https://avatars.githubusercontent.com/u/7765807?v=3","gravatar_id":"","url":"https://api.github.com/users/kloetzl","html_url":"https://github.com/kloetzl","followers_url":"https://api.github.com/users/kloetzl/followers","following_url":"https://api.github.com/users/kloetzl/following{/other_user}","gists_url":"https://api.github.com/users/kloetzl/gists{/gist_id}","starred_url":"https://api.github.com/users/kloetzl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kloetzl/subscriptions","organizations_url":"https://api.github.com/users/kloetzl/orgs","repos_url":"https://api.github.com/users/kloetzl/repos","events_url":"https://api.github.com/users/kloetzl/events{/privacy}","received_events_url":"https://api.github.com/users/kloetzl/received_events","type":"User","site_admin":false},"created_at":"2015-09-11T13:05:41Z","updated_at":"2015-09-11T13:05:41Z","body":"> Main memory accesses will average around 200 cycles, especially if you pre-sort your search keys, but most CPUs will do a TLB refill for every new page accessed and this I have measured at around 3000 cycles. This is mitigated somewhat as the accesses are done in parallel using the 8 or so retirement slots available in a typical core's memory unit.\r\n\r\nI never used to care about the TLB. But 3000 cycles sounds scary. Do you have a readup for me?\r\n\r\n> I don't have the time to check to see if these ideas are unique and don't care much. More important is to deliver a reliable searching service that generates 100% of the available results. This code is far from optimal and it will be improved once the user base is established.\r\n\r\nBasically, the Readme is missing a sentence on the problem you are trying to solve with the suffix array i.e. a lot of short lookups."}}