{"action":"created","issue":{"url":"https://api.github.com/repos/10XGenomics/STAR/issues/1","repository_url":"https://api.github.com/repos/10XGenomics/STAR","labels_url":"https://api.github.com/repos/10XGenomics/STAR/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/10XGenomics/STAR/issues/1/comments","events_url":"https://api.github.com/repos/10XGenomics/STAR/issues/1/events","html_url":"https://github.com/10XGenomics/STAR/pull/1","id":387640268,"node_id":"MDExOlB1bGxSZXF1ZXN0MjM2MDgyNjIy","number":1,"title":"Fix Segmentation Fault Under Certain Conditions","user":{"login":"evolvedmicrobe","id":1330626,"node_id":"MDQ6VXNlcjEzMzA2MjY=","avatar_url":"https://avatars0.githubusercontent.com/u/1330626?v=4","gravatar_id":"","url":"https://api.github.com/users/evolvedmicrobe","html_url":"https://github.com/evolvedmicrobe","followers_url":"https://api.github.com/users/evolvedmicrobe/followers","following_url":"https://api.github.com/users/evolvedmicrobe/following{/other_user}","gists_url":"https://api.github.com/users/evolvedmicrobe/gists{/gist_id}","starred_url":"https://api.github.com/users/evolvedmicrobe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/evolvedmicrobe/subscriptions","organizations_url":"https://api.github.com/users/evolvedmicrobe/orgs","repos_url":"https://api.github.com/users/evolvedmicrobe/repos","events_url":"https://api.github.com/users/evolvedmicrobe/events{/privacy}","received_events_url":"https://api.github.com/users/evolvedmicrobe/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-12-05T08:17:50Z","updated_at":"2018-12-05T09:06:44Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/10XGenomics/STAR/pulls/1","html_url":"https://github.com/10XGenomics/STAR/pull/1","diff_url":"https://github.com/10XGenomics/STAR/pull/1.diff","patch_url":"https://github.com/10XGenomics/STAR/pull/1.patch"},"body":"This PR was motivated by a SIGSEGV that STAR produced when aligning a particular read against the Rabbit genome.  Explanation of the problem and fix below.\r\n\r\nThe issue was as follows.  In trying to map the read, the aligner routine within `ReadAlign::maxMappableLength2strands` was trying to find exact matches for the end of the read.  The first step in this process is looking up a given prefix length in the suffix array index.  This index contains minimum (and maximum) locations for prefixes up to size L_max (14 in this case).  For this particular read segment, no prefix of size 14 was found, so the program re-attempted to search the index with a prefix of size 13, which it did find.  Because a prefix of size 13 and not 14 was found, the program knew there was no match of size 14 and so tried to set the end of the search range in the suffix array (`indStartEnd[1]`) using a short-cut that avoids the binary search.  In particular, it set the End of the bounded range to the value of one minus the next element in the index.\r\n\r\nHowever, it appears not all elements prior to the start of the next prefix are guaranteed to match the current prefix.  In this particular case, that next element pointed to a position 10 bases before the end of the genome, which meant it could not produce an alignment 13 bases in length.  Later on inside `ReadAlign::stitchPieces` and its call to `sjSplitAlign` this led to the SIGSEGV when while calculating the alignment start position it inferred to be 3 basepairs past the end of the genome, giving an offset position of `-3` which when converted to an unsigned integer has value `18446744073709551613`, and consequentally the calculated value for `isj` in the code line `P->sjDstart[isj]` referred to unmapped memory, leading to the SIGSEGV.\r\n\r\nI believe this can happen as the suffix array can be sorted as follows:\r\n\r\n    ACGTACGTACGTAA # Matching prefix of size 13\r\n    ACGTACGTACGTAN # Suffix array element with padded-bases/Ns, but not a valid 13-mer alignment\r\n    ACGTACGTACGTCA # Next prefix of size 13\r\n\r\nSince it seemed the short-cut avoiding the binary-search was not reliable, I removed it with this commit.  Since it also appeared that this was a general problem where one could not guarantee the initial range guessed held matching prefixes up to the length tested (but rather only the length tested minus 1), I also changed the binary search to account for this.  Testing showed for this case it restored the correct behavior in the inferred bounds, such that the alignment length was consistent across the start and end of the array element range set."},"comment":{"url":"https://api.github.com/repos/10XGenomics/STAR/issues/comments/444411459","html_url":"https://github.com/10XGenomics/STAR/pull/1#issuecomment-444411459","issue_url":"https://api.github.com/repos/10XGenomics/STAR/issues/1","id":444411459,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0NDQxMTQ1OQ==","user":{"login":"evolvedmicrobe","id":1330626,"node_id":"MDQ6VXNlcjEzMzA2MjY=","avatar_url":"https://avatars0.githubusercontent.com/u/1330626?v=4","gravatar_id":"","url":"https://api.github.com/users/evolvedmicrobe","html_url":"https://github.com/evolvedmicrobe","followers_url":"https://api.github.com/users/evolvedmicrobe/followers","following_url":"https://api.github.com/users/evolvedmicrobe/following{/other_user}","gists_url":"https://api.github.com/users/evolvedmicrobe/gists{/gist_id}","starred_url":"https://api.github.com/users/evolvedmicrobe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/evolvedmicrobe/subscriptions","organizations_url":"https://api.github.com/users/evolvedmicrobe/orgs","repos_url":"https://api.github.com/users/evolvedmicrobe/repos","events_url":"https://api.github.com/users/evolvedmicrobe/events{/privacy}","received_events_url":"https://api.github.com/users/evolvedmicrobe/received_events","type":"User","site_admin":false},"created_at":"2018-12-05T09:06:44Z","updated_at":"2018-12-05T09:06:44Z","author_association":"NONE","body":"Fixed WIP issue"}}
{"actor":{"display_login":"evolvedmicrobe"}}