search

pangenome / pggb

the pangenome graph builder
https://doi.org/10.1038/s41592-024-02430-3
MIT License
368 stars 41 forks source link

Downsampling strategy for the `wfmash` alignment graph #149

Closed subwaystation closed 2 years ago

subwaystation commented 2 years ago

As pointed out by @ekg, the all versus all alignment strategy is quadratically expensive. Which might be too much for certain problem sizes. One solution might be to sparsify the wfmash alignment graph after mapping and before aligning. Locally, we can remove edges in the alignment graph without breaking any components in the original all-to-all graph.

AndreaGuarracino commented 2 years ago

Tackled in https://github.com/waveygang/wfmash/pull/136