# Spectral Cluster Supertree
[](https://pypi.org/project/sc-supertree/)
[](https://pypi.org/project/sc-supertree/)
[](https://github.com/psf/black)
[](https://github.com/rmcar17/SpectralClusterSupertree/actions/workflows/ci.yml)
[](https://coveralls.io/github/rmcar17/SpectralClusterSupertree?branch=main)
[](https://github.com/rmcar17/SpectralClusterSupertree/blob/main/LICENSE)
Spectral Cluster Supertree is a state-of-the-art algorithm for constructing rooted supertrees from collections of rooted source trees.
Spectral Cluster Supertree can be used on Newick formatted trees in Python in conjunction with [cogent3](https://github.com/cogent3/cogent3)'s tree objects, or invoked from the command line.
Spectral Cluster Supertree can employ a number of weighting strategies that take into account the depths of nodes in the trees, as well as branch lengths. A user can specify weights of trees to add bias to some of the source trees if desired.
## Installation
```bash
pip install sc-supertree
```
## Usage
### Python
```python
from sc_supertree import load_trees, construct_supertree
source_trees = load_trees("source_tree_file.tre")
supertree = construct_supertree(source_trees, pcg_weighting="branch")
supertree.write("supertree_file.tre")
```
### CLI
In your environment which has spectral-cluster-supertree installed:
```bash
scs -i SOURCE_TREE_FILE -o SUPERTREE_FILE -p PCG_WEIGHTING_STRATEGY
```
The ```-i``` and ```-o``` options for the input and output files are required.
The ```-p``` *proper cluster graph* weighting strategy option must be one of ```ONE|DEPTH|BRANCH```. It defaults to ```BRANCH``` when not provided (not recommended when some trees are missing branch lenghts - see below).
## Weighting Strategies
### Proper Cluster Graph Weighting
Spectral Cluster Supertree recursively paritions the complete set of taxa to form a supertree. The core component of the algorithm involves partitioning the *proper cluster graph* through spectral clustering when the source trees are not consistent.
The *proper cluster graph* has the set of all taxa in the source trees as its vertices, and an edge connects two taxa if they appear together on the same side of the root in any of the source trees (such pairs of taxa are called **proper clusters**). Let $lca$ be the lowest common ancestor of a proper cluster. Each edge is weighted according to the specified strategy:
- **one** - The number of trees in which the pair of taxa appear as a proper cluster in.
- **depth** - The sum of the depths of the $lca$ of the proper cluster in all of the source trees.
- **branch** - The sum of the root to $lca$ branch lengths of the proper cluster in all of the source trees. If branch lengths are missing defaults to one (equivalent to depth). Do not use if some trees are missing branch lengths.
The **branch** weighting strategy is recommened where branch lengths are available. Otherwise, the **depth** weighting strategy is recommended over the **one** weighting strategy.
### Tree Weighting
In addition to the above, users may associate trees with weights to bias the results towards specific trees. Prior to the summation of the weights for an edge in the *proper cluster graph*, they are multiplied by the weight of the corresponding tree. The weight of each tree defaults to one if not specified.
An example is shown below, without the tree weights the alogrithm would randomly return either triple.
```python
>>> from sc_supertree import construct_supertree
>>> from cogent3 import make_tree
>>> tree_1 = make_tree("(a,(b,c))")
>>> tree_2 = make_tree("(c,(b,a))")
>>> print(construct_supertree([tree_1, tree_2], weights=[1, 1.5]))
(c,(b,a));
```
Tree weighting can only be used in the python implementation, not the CLI.
Raw data
{
"_id": null,
"home_page": null,
"name": "sc-supertree",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10,<3.13",
"maintainer_email": null,
"keywords": "supertree,phylogeny,biology,bioinformatics",
"author": "Robert McArthur",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/4b/0d/74a5ef4518ab05836c49e47ddaa60faeff22ffda6e3c1ef1bd8ebfa4626a/sc-supertree-2024.2.29.post1.tar.gz",
"platform": null,
"description": "# Spectral Cluster Supertree\n\n[](https://pypi.org/project/sc-supertree/)\n[](https://pypi.org/project/sc-supertree/)\n[](https://github.com/psf/black)\n\n[](https://github.com/rmcar17/SpectralClusterSupertree/actions/workflows/ci.yml)\n[](https://coveralls.io/github/rmcar17/SpectralClusterSupertree?branch=main)\n[](https://github.com/rmcar17/SpectralClusterSupertree/blob/main/LICENSE)\n\nSpectral Cluster Supertree is a state-of-the-art algorithm for constructing rooted supertrees from collections of rooted source trees.\n\nSpectral Cluster Supertree can be used on Newick formatted trees in Python in conjunction with [cogent3](https://github.com/cogent3/cogent3)'s tree objects, or invoked from the command line.\n\nSpectral Cluster Supertree can employ a number of weighting strategies that take into account the depths of nodes in the trees, as well as branch lengths. A user can specify weights of trees to add bias to some of the source trees if desired.\n\n## Installation\n\n```bash\npip install sc-supertree\n```\n\n## Usage\n\n### Python\n\n```python\nfrom sc_supertree import load_trees, construct_supertree\n\nsource_trees = load_trees(\"source_tree_file.tre\")\n\nsupertree = construct_supertree(source_trees, pcg_weighting=\"branch\")\n\nsupertree.write(\"supertree_file.tre\")\n```\n\n### CLI\n\nIn your environment which has spectral-cluster-supertree installed:\n\n```bash\nscs -i SOURCE_TREE_FILE -o SUPERTREE_FILE -p PCG_WEIGHTING_STRATEGY\n```\n\nThe ```-i``` and ```-o``` options for the input and output files are required.\n\nThe ```-p``` *proper cluster graph* weighting strategy option must be one of ```ONE|DEPTH|BRANCH```. It defaults to ```BRANCH``` when not provided (not recommended when some trees are missing branch lenghts - see below).\n\n## Weighting Strategies\n\n### Proper Cluster Graph Weighting\n\nSpectral Cluster Supertree recursively paritions the complete set of taxa to form a supertree. The core component of the algorithm involves partitioning the *proper cluster graph* through spectral clustering when the source trees are not consistent.\n\nThe *proper cluster graph* has the set of all taxa in the source trees as its vertices, and an edge connects two taxa if they appear together on the same side of the root in any of the source trees (such pairs of taxa are called **proper clusters**). Let $lca$ be the lowest common ancestor of a proper cluster. Each edge is weighted according to the specified strategy:\n\n- **one** - The number of trees in which the pair of taxa appear as a proper cluster in.\n- **depth** - The sum of the depths of the $lca$ of the proper cluster in all of the source trees.\n- **branch** - The sum of the root to $lca$ branch lengths of the proper cluster in all of the source trees. If branch lengths are missing defaults to one (equivalent to depth). Do not use if some trees are missing branch lengths.\n\nThe **branch** weighting strategy is recommened where branch lengths are available. Otherwise, the **depth** weighting strategy is recommended over the **one** weighting strategy.\n\n### Tree Weighting\n\nIn addition to the above, users may associate trees with weights to bias the results towards specific trees. Prior to the summation of the weights for an edge in the *proper cluster graph*, they are multiplied by the weight of the corresponding tree. The weight of each tree defaults to one if not specified.\n\nAn example is shown below, without the tree weights the alogrithm would randomly return either triple.\n\n```python\n>>> from sc_supertree import construct_supertree\n>>> from cogent3 import make_tree\n>>> tree_1 = make_tree(\"(a,(b,c))\")\n>>> tree_2 = make_tree(\"(c,(b,a))\")\n>>> print(construct_supertree([tree_1, tree_2], weights=[1, 1.5]))\n(c,(b,a));\n```\n\nTree weighting can only be used in the python implementation, not the CLI.\n",
"bugtrack_url": null,
"license": null,
"summary": "Spectral Cluster Supertree",
"version": "2024.2.29.post1",
"project_urls": {
"Bug Tracker": "https://github.com/rmcar17/SpectralClusterSupertree/issues",
"Source Code": "https://github.com/rmcar17/SpectralClusterSupertree"
},
"split_keywords": [
"supertree",
"phylogeny",
"biology",
"bioinformatics"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "d7e0b9b7951ae1bd03790d42852beb59b89c407661c1f8ca3db731a63067eddf",
"md5": "c8791ee382203302e798fa3b643d7c81",
"sha256": "3ee8c30554e4505ea5f65ada4afdd1d33b6df4681b65364b523059419284b096"
},
"downloads": -1,
"filename": "sc_supertree-2024.2.29.post1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c8791ee382203302e798fa3b643d7c81",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.10,<3.13",
"size": 11412,
"upload_time": "2024-02-29T00:49:57",
"upload_time_iso_8601": "2024-02-29T00:49:57.720237Z",
"url": "https://files.pythonhosted.org/packages/d7/e0/b9b7951ae1bd03790d42852beb59b89c407661c1f8ca3db731a63067eddf/sc_supertree-2024.2.29.post1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "4b0d74a5ef4518ab05836c49e47ddaa60faeff22ffda6e3c1ef1bd8ebfa4626a",
"md5": "d2b0af8d41cdd7a39831bab7dae66e80",
"sha256": "65e42327017db847e1653b3077d34923404359d07fd106521d83240e1a0f0ff6"
},
"downloads": -1,
"filename": "sc-supertree-2024.2.29.post1.tar.gz",
"has_sig": false,
"md5_digest": "d2b0af8d41cdd7a39831bab7dae66e80",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10,<3.13",
"size": 87663,
"upload_time": "2024-02-29T00:50:12",
"upload_time_iso_8601": "2024-02-29T00:50:12.498484Z",
"url": "https://files.pythonhosted.org/packages/4b/0d/74a5ef4518ab05836c49e47ddaa60faeff22ffda6e3c1ef1bd8ebfa4626a/sc-supertree-2024.2.29.post1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-02-29 00:50:12",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "rmcar17",
"github_project": "SpectralClusterSupertree",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "sc-supertree"
}
JSON
