{"action":"created","comment":{"url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/comments/90198363","pull_request_review_id":10719570,"id":90198363,"diff_hunk":"@@ -0,0 +1,218 @@\n+// Copyright 2014-2015 Patrick Marks\n+// Licensed under the MIT license (http://opensource.org/licenses/MIT)\n+// This file may not be copied, modified, or distributed\n+// except according to those terms.\n+\n+//! Calculate 'sparse' alignments from kmer matches. Can be much faster than \n+//! Smith-Waterman for long string, when a large enough k is used. \n+//! Complexity: O(n * log(n)) for a pair of strings with n k-kmer matches. This\n+//! approach is useful for generating an approximate 'backbone' alignments \n+//! between two long sequences, for example in long-read alignment or \n+//! genome-genome alignment. The backbone alignment can be used as-is, or can serve\n+//! as a guide for a banded alignment.  By tuning k so that len(query) + len(reference) < 4^k,\n+//! the number of false positive kmer matches is kept small, resulting in very\n+//! fast run times for long strings.\n+//!\n+//! # Example\n+//!\n+//! ```\n+//! use bio::alignment::sparse::*;\n+//!\n+//! let s1 =   \"ACGTACGATAGGTA\";\n+//! let s2 = \"TTACGTACGATAGGTATT\";\n+//! let k = 8;\n+//! let matches = find_kmer_matches(&s1, &s2, k);\n+//! let (tb, score,  _) = lcskpp(&matches, k);\n+//! let match_path: Vec<(u32,u32)> = tb.iter().map(|i| matches[*i]).collect();\n+//! assert_eq!(match_path, vec![(0,2), (1,3), (2,4), (3,5), (4,6), (5,7), (6,8)]);\n+//! assert_eq!(score, 14);\n+\n+use std::cmp::max;\n+use data_structures::bit_tree::MaxBitTree;\n+use data_structures::qgram_index::QGramIndex;\n+use alphabets::Alphabet;\n+\n+/// Sparse DP routine for Longest Common Subsequence in length k substrings.  Also known of LCSk++\n+/// From LCSk++: Practical similarity metric for long strings. Filip Pavetić, Goran Žužić, Mile Šikić\n+/// Paper here :https://arxiv.org/abs/1407.2407.  Original implementation here: https://github.com/fpavetic/lcskpp\n+/// matches is a tuple of the positions of all k-mer matches between two strings. matches vector must be sorted by caller.\n+/// The first element of the return tuple is the LCSk++ path, represented as vector of indices into the matches vector.\n+/// The second element of the return tuple is the score of the path, which is the number of bases covered by the matched kmers.\n+/// The third element of the return tuple is full DP vector, which can generally be ignored. (It may be useful for testing purposes).","path":"src/alignment/sparse.rs","position":41,"original_position":41,"commit_id":"bedecfcd1752778a13dd0b072169144e1316853b","original_commit_id":"bedecfcd1752778a13dd0b072169144e1316853b","user":{"login":"johanneskoester","id":1858646,"avatar_url":"https://avatars.githubusercontent.com/u/1858646?v=3","gravatar_id":"","url":"https://api.github.com/users/johanneskoester","html_url":"https://github.com/johanneskoester","followers_url":"https://api.github.com/users/johanneskoester/followers","following_url":"https://api.github.com/users/johanneskoester/following{/other_user}","gists_url":"https://api.github.com/users/johanneskoester/gists{/gist_id}","starred_url":"https://api.github.com/users/johanneskoester/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/johanneskoester/subscriptions","organizations_url":"https://api.github.com/users/johanneskoester/orgs","repos_url":"https://api.github.com/users/johanneskoester/repos","events_url":"https://api.github.com/users/johanneskoester/events{/privacy}","received_events_url":"https://api.github.com/users/johanneskoester/received_events","type":"User","site_admin":false},"body":"Can you use a similar formatting than in other doc comments of Rust-Bio (i.e. an list of args etc.)?","created_at":"2016-11-30T09:44:43Z","updated_at":"2016-11-30T09:52:07Z","html_url":"https://github.com/rust-bio/rust-bio/pull/102#discussion_r90198363","pull_request_url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102","_links":{"self":{"href":"https://api.github.com/repos/rust-bio/rust-bio/pulls/comments/90198363"},"html":{"href":"https://github.com/rust-bio/rust-bio/pull/102#discussion_r90198363"},"pull_request":{"href":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102"}}},"pull_request":{"url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102","id":94872382,"html_url":"https://github.com/rust-bio/rust-bio/pull/102","diff_url":"https://github.com/rust-bio/rust-bio/pull/102.diff","patch_url":"https://github.com/rust-bio/rust-bio/pull/102.patch","issue_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/102","number":102,"state":"open","locked":false,"title":"LCSk++ / sparse DP routine","user":{"login":"pmarks","id":45827,"avatar_url":"https://avatars.githubusercontent.com/u/45827?v=3","gravatar_id":"","url":"https://api.github.com/users/pmarks","html_url":"https://github.com/pmarks","followers_url":"https://api.github.com/users/pmarks/followers","following_url":"https://api.github.com/users/pmarks/following{/other_user}","gists_url":"https://api.github.com/users/pmarks/gists{/gist_id}","starred_url":"https://api.github.com/users/pmarks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pmarks/subscriptions","organizations_url":"https://api.github.com/users/pmarks/orgs","repos_url":"https://api.github.com/users/pmarks/repos","events_url":"https://api.github.com/users/pmarks/events{/privacy}","received_events_url":"https://api.github.com/users/pmarks/received_events","type":"User","site_admin":false},"body":"Sparse DP routine for Longest Common Subsequence in length k substrings. Also known of LCSk++\r\nFrom LCSk++: Practical similarity metric for long strings. Filip Pavetić, Goran Žužić, Mile Šikić\r\nPaper here :https://arxiv.org/abs/1407.2407.  Original implementation here: https://github.com/fpavetic/lcskpp\r\n","created_at":"2016-11-22T18:35:10Z","updated_at":"2016-11-30T09:52:07Z","closed_at":null,"merged_at":null,"merge_commit_sha":"73aa04dd28ee3aa6627b4c363741ba9ba09c47e8","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102/commits","review_comments_url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102/comments","review_comment_url":"https://api.github.com/repos/rust-bio/rust-bio/pulls/comments{/number}","comments_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/102/comments","statuses_url":"https://api.github.com/repos/rust-bio/rust-bio/statuses/bedecfcd1752778a13dd0b072169144e1316853b","head":{"label":"pmarks:pmarks/sparse-dp","ref":"pmarks/sparse-dp","sha":"bedecfcd1752778a13dd0b072169144e1316853b","user":{"login":"pmarks","id":45827,"avatar_url":"https://avatars.githubusercontent.com/u/45827?v=3","gravatar_id":"","url":"https://api.github.com/users/pmarks","html_url":"https://github.com/pmarks","followers_url":"https://api.github.com/users/pmarks/followers","following_url":"https://api.github.com/users/pmarks/following{/other_user}","gists_url":"https://api.github.com/users/pmarks/gists{/gist_id}","starred_url":"https://api.github.com/users/pmarks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pmarks/subscriptions","organizations_url":"https://api.github.com/users/pmarks/orgs","repos_url":"https://api.github.com/users/pmarks/repos","events_url":"https://api.github.com/users/pmarks/events{/privacy}","received_events_url":"https://api.github.com/users/pmarks/received_events","type":"User","site_admin":false},"repo":{"id":60558125,"name":"rust-bio","full_name":"pmarks/rust-bio","owner":{"login":"pmarks","id":45827,"avatar_url":"https://avatars.githubusercontent.com/u/45827?v=3","gravatar_id":"","url":"https://api.github.com/users/pmarks","html_url":"https://github.com/pmarks","followers_url":"https://api.github.com/users/pmarks/followers","following_url":"https://api.github.com/users/pmarks/following{/other_user}","gists_url":"https://api.github.com/users/pmarks/gists{/gist_id}","starred_url":"https://api.github.com/users/pmarks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pmarks/subscriptions","organizations_url":"https://api.github.com/users/pmarks/orgs","repos_url":"https://api.github.com/users/pmarks/repos","events_url":"https://api.github.com/users/pmarks/events{/privacy}","received_events_url":"https://api.github.com/users/pmarks/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/pmarks/rust-bio","description":"This library provides implementations of many algorithms and data structures that are useful for bioinformatics. All provided implementations are rigorously tested via continuous integration.","fork":true,"url":"https://api.github.com/repos/pmarks/rust-bio","forks_url":"https://api.github.com/repos/pmarks/rust-bio/forks","keys_url":"https://api.github.com/repos/pmarks/rust-bio/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pmarks/rust-bio/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pmarks/rust-bio/teams","hooks_url":"https://api.github.com/repos/pmarks/rust-bio/hooks","issue_events_url":"https://api.github.com/repos/pmarks/rust-bio/issues/events{/number}","events_url":"https://api.github.com/repos/pmarks/rust-bio/events","assignees_url":"https://api.github.com/repos/pmarks/rust-bio/assignees{/user}","branches_url":"https://api.github.com/repos/pmarks/rust-bio/branches{/branch}","tags_url":"https://api.github.com/repos/pmarks/rust-bio/tags","blobs_url":"https://api.github.com/repos/pmarks/rust-bio/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pmarks/rust-bio/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pmarks/rust-bio/git/refs{/sha}","trees_url":"https://api.github.com/repos/pmarks/rust-bio/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pmarks/rust-bio/statuses/{sha}","languages_url":"https://api.github.com/repos/pmarks/rust-bio/languages","stargazers_url":"https://api.github.com/repos/pmarks/rust-bio/stargazers","contributors_url":"https://api.github.com/repos/pmarks/rust-bio/contributors","subscribers_url":"https://api.github.com/repos/pmarks/rust-bio/subscribers","subscription_url":"https://api.github.com/repos/pmarks/rust-bio/subscription","commits_url":"https://api.github.com/repos/pmarks/rust-bio/commits{/sha}","git_commits_url":"https://api.github.com/repos/pmarks/rust-bio/git/commits{/sha}","comments_url":"https://api.github.com/repos/pmarks/rust-bio/comments{/number}","issue_comment_url":"https://api.github.com/repos/pmarks/rust-bio/issues/comments{/number}","contents_url":"https://api.github.com/repos/pmarks/rust-bio/contents/{+path}","compare_url":"https://api.github.com/repos/pmarks/rust-bio/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pmarks/rust-bio/merges","archive_url":"https://api.github.com/repos/pmarks/rust-bio/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pmarks/rust-bio/downloads","issues_url":"https://api.github.com/repos/pmarks/rust-bio/issues{/number}","pulls_url":"https://api.github.com/repos/pmarks/rust-bio/pulls{/number}","milestones_url":"https://api.github.com/repos/pmarks/rust-bio/milestones{/number}","notifications_url":"https://api.github.com/repos/pmarks/rust-bio/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pmarks/rust-bio/labels{/name}","releases_url":"https://api.github.com/repos/pmarks/rust-bio/releases{/id}","deployments_url":"https://api.github.com/repos/pmarks/rust-bio/deployments","created_at":"2016-06-06T20:21:01Z","updated_at":"2016-06-06T20:21:02Z","pushed_at":"2016-11-29T21:19:31Z","git_url":"git://github.com/pmarks/rust-bio.git","ssh_url":"git@github.com:pmarks/rust-bio.git","clone_url":"https://github.com/pmarks/rust-bio.git","svn_url":"https://github.com/pmarks/rust-bio","homepage":"https://rust-bio.github.io","size":3781,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"rust-bio:master","ref":"master","sha":"f1047bdc202126772aba927ce5052ea39251f10e","user":{"login":"rust-bio","id":13785584,"avatar_url":"https://avatars.githubusercontent.com/u/13785584?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-bio","html_url":"https://github.com/rust-bio","followers_url":"https://api.github.com/users/rust-bio/followers","following_url":"https://api.github.com/users/rust-bio/following{/other_user}","gists_url":"https://api.github.com/users/rust-bio/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-bio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-bio/subscriptions","organizations_url":"https://api.github.com/users/rust-bio/orgs","repos_url":"https://api.github.com/users/rust-bio/repos","events_url":"https://api.github.com/users/rust-bio/events{/privacy}","received_events_url":"https://api.github.com/users/rust-bio/received_events","type":"Organization","site_admin":false},"repo":{"id":29821195,"name":"rust-bio","full_name":"rust-bio/rust-bio","owner":{"login":"rust-bio","id":13785584,"avatar_url":"https://avatars.githubusercontent.com/u/13785584?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-bio","html_url":"https://github.com/rust-bio","followers_url":"https://api.github.com/users/rust-bio/followers","following_url":"https://api.github.com/users/rust-bio/following{/other_user}","gists_url":"https://api.github.com/users/rust-bio/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-bio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-bio/subscriptions","organizations_url":"https://api.github.com/users/rust-bio/orgs","repos_url":"https://api.github.com/users/rust-bio/repos","events_url":"https://api.github.com/users/rust-bio/events{/privacy}","received_events_url":"https://api.github.com/users/rust-bio/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/rust-bio/rust-bio","description":"This library provides implementations of many algorithms and data structures that are useful for bioinformatics. All provided implementations are rigorously tested via continuous integration.","fork":false,"url":"https://api.github.com/repos/rust-bio/rust-bio","forks_url":"https://api.github.com/repos/rust-bio/rust-bio/forks","keys_url":"https://api.github.com/repos/rust-bio/rust-bio/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rust-bio/rust-bio/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rust-bio/rust-bio/teams","hooks_url":"https://api.github.com/repos/rust-bio/rust-bio/hooks","issue_events_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/events{/number}","events_url":"https://api.github.com/repos/rust-bio/rust-bio/events","assignees_url":"https://api.github.com/repos/rust-bio/rust-bio/assignees{/user}","branches_url":"https://api.github.com/repos/rust-bio/rust-bio/branches{/branch}","tags_url":"https://api.github.com/repos/rust-bio/rust-bio/tags","blobs_url":"https://api.github.com/repos/rust-bio/rust-bio/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rust-bio/rust-bio/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rust-bio/rust-bio/git/refs{/sha}","trees_url":"https://api.github.com/repos/rust-bio/rust-bio/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rust-bio/rust-bio/statuses/{sha}","languages_url":"https://api.github.com/repos/rust-bio/rust-bio/languages","stargazers_url":"https://api.github.com/repos/rust-bio/rust-bio/stargazers","contributors_url":"https://api.github.com/repos/rust-bio/rust-bio/contributors","subscribers_url":"https://api.github.com/repos/rust-bio/rust-bio/subscribers","subscription_url":"https://api.github.com/repos/rust-bio/rust-bio/subscription","commits_url":"https://api.github.com/repos/rust-bio/rust-bio/commits{/sha}","git_commits_url":"https://api.github.com/repos/rust-bio/rust-bio/git/commits{/sha}","comments_url":"https://api.github.com/repos/rust-bio/rust-bio/comments{/number}","issue_comment_url":"https://api.github.com/repos/rust-bio/rust-bio/issues/comments{/number}","contents_url":"https://api.github.com/repos/rust-bio/rust-bio/contents/{+path}","compare_url":"https://api.github.com/repos/rust-bio/rust-bio/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rust-bio/rust-bio/merges","archive_url":"https://api.github.com/repos/rust-bio/rust-bio/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rust-bio/rust-bio/downloads","issues_url":"https://api.github.com/repos/rust-bio/rust-bio/issues{/number}","pulls_url":"https://api.github.com/repos/rust-bio/rust-bio/pulls{/number}","milestones_url":"https://api.github.com/repos/rust-bio/rust-bio/milestones{/number}","notifications_url":"https://api.github.com/repos/rust-bio/rust-bio/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rust-bio/rust-bio/labels{/name}","releases_url":"https://api.github.com/repos/rust-bio/rust-bio/releases{/id}","deployments_url":"https://api.github.com/repos/rust-bio/rust-bio/deployments","created_at":"2015-01-25T16:40:31Z","updated_at":"2016-11-27T03:05:55Z","pushed_at":"2016-11-29T21:19:31Z","git_url":"git://github.com/rust-bio/rust-bio.git","ssh_url":"git@github.com:rust-bio/rust-bio.git","clone_url":"https://github.com/rust-bio/rust-bio.git","svn_url":"https://github.com/rust-bio/rust-bio","homepage":"https://rust-bio.github.io","size":9000,"stargazers_count":244,"watchers_count":244,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":35,"mirror_url":null,"open_issues_count":17,"forks":35,"open_issues":17,"watchers":244,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102"},"html":{"href":"https://github.com/rust-bio/rust-bio/pull/102"},"issue":{"href":"https://api.github.com/repos/rust-bio/rust-bio/issues/102"},"comments":{"href":"https://api.github.com/repos/rust-bio/rust-bio/issues/102/comments"},"review_comments":{"href":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102/comments"},"review_comment":{"href":"https://api.github.com/repos/rust-bio/rust-bio/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/rust-bio/rust-bio/pulls/102/commits"},"statuses":{"href":"https://api.github.com/repos/rust-bio/rust-bio/statuses/bedecfcd1752778a13dd0b072169144e1316853b"}}}}
{"actor":{"display_login":"johanneskoester"}}