Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

add 'cluster' and 'cocluster' to sourmash #700

Open
ctb opened this issue Jul 20, 2019 · 3 comments
Open

add 'cluster' and 'cocluster' to sourmash #700

ctb opened this issue Jul 20, 2019 · 3 comments
Labels
enhancement plugin_todo Write a plugin for this!

Comments

@ctb
Copy link
Contributor

ctb commented Jul 20, 2019

the cocluster script may be useful for people comparing the output of binning.

see also #459
@ctb
Copy link
Contributor Author

ctb commented Jul 20, 2019 •
edited
Loading 

% python cocluster.py --first podar-ref/63.fa.sig --second podar-ref/63.fa.sig podar-ref/2.fa.sig  -k 31 --cut-point=1.0
first list contains 1 files; second list contains 2 files.
... loading file 0 of 1 for first list
... loading file 1 of 2 for second list
ksize: 31 / moltype: DNA
downsampling to scaled value of 1000
first list contains 1 signatures; second list contains 2 signatures.
...comparing 3 signatures, all by all

0-NC_011663.1 She...    [1. 1. 0.]
1-NC_011663.1 She...    [1. 1. 0.]
2-CP001071.1 Akke...    [0. 0. 1.]
min similarity in matrix: 0.000
** wrote coclust dendrogram to sourmash.coclust.dendro.pdf
cluster 2 is 1 in size
         CP001071.1 Akkermansia muciniphila ATCC BAA-835, complete genome
cluster 1 is 2 in size
         NC_011663.1 Shewanella baltica OS223, complete genome
         NC_011663.1 Shewanella baltica OS223, complete genome
** wrote coclust assignments spreadsheet to sourmash.coclust.csv

@ctb
Copy link
Contributor Author

ctb commented Jan 10, 2021

see also #1265, uniqify script, which I think is nice and simple.

@ctb
Copy link
Contributor Author

ctb commented Mar 4, 2021

may be good as a plugin test #1353

This was referenced Mar 4, 2021
Open
Open
@ctb ctb mentioned this issue Jul 31, 2023
Open
@ctb ctb added the plugin_todo Write a plugin for this! label Sep 23, 2023
@ctb ctb mentioned this issue Feb 26, 2024
Merged
bluegenes added a commit to sourmash-bio/sourmash_plugin_branchwater that referenced this issue Feb 27, 2024
@bluegenes @ctb
MRG: Add graph-based clustering (#234)
6d754b5 
This PR adds a new command, `cluster`, that can be used to cluster the output from `pairwise` and `multisearch`.

`cluster`uses `rustworkx-core` (which internally uses `petgraph`) to build a graph, adding edges between nodes when the similarity exceeds the user-defined threshold. It can work on any of the similarity columns output by `pairwise` or `multisearch`, and will add all nodes to the graph to preserve singleton 'clusters' in the output.

`cluster` outputs two files: 
1. cluster identities file: `Component_X, name1;name2;name3...`
2. cluster size histogram `cluster_size, count`

context for some things I tried:
- try using petgraph directly and removing rustworkx dependency
> nope,`rustworkx-core` adds `connected_components` that returns the connected components, rather than just the number of connected components. Could reimplement if `rustworkx-core` brings in a lot of deps
- try using 'extend_with_edges' instead of add_edge logic.
> nope, only in `petgraph`

**Punted Issues:**
- develop clustering visualizations (ref @mr-eyes kSpider/dbretina work). Optionally output dot file of graph? (#248)
- enable updating clusters, rather than always regenerating from scratch (#249)
- benchmark `cluster` (#247)
>  `pairwise` files can be millions of lines long. Would it be faster to parallel read them, store them in an `edges` vector, and then add nodes/edges sequentially? Note that we would probably need to either 1. store all edges, including those that do not pass threshold) or 2. After building the graph from edges, add nodes from `names_to_node` that are not already in the graph to preserve singletons.


Related issues:

* #219
* sourmash-bio/sourmash#2271
* sourmash-bio/sourmash#700
* sourmash-bio/sourmash#225
* sourmash-bio/sourmash#274


---------

Co-authored-by: C. Titus Brown <titus@idyll.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement plugin_todo Write a plugin for this!
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@luizirber @ctb