Description:

fastsubtrees 2.1

Fastsubtrees
Fastsubtrees is a Python library and a command line script, for handling fairly
large trees (in the order of magnitude of millions nodes), in particular
allowing the fast extraction of any subtree.
The main application domain of fastsubtrees is working with the NCBI taxonomy
tree, however the code is implemented in a generic way, so that other
applications are possible.
The library functionality can be accessed both from inside Python code
and from the provided command line tool fastsubtrees.
Introduction
For the use of fastsubtrees, nodes must be uniquely identified by non-negative IDs.
Furthermore, the space of the IDs must be compact (i.e. the maximum ID should not be
much larger than the number of IDs).
The first step when using fastsubtrees is to construct a tree representation.
The operation requires a source of IDs of elements and their parents, which can be
a tabular file, or any Python function yielding the IDs.
This operation just takes a few seconds, for a tree with million nodes, such as the NCBI taxonomy tree.
It must be done only once, if a tree does not change, since the resulting data
is stored to file.
The IDs of the NCBI taxonomy tree fullfill the conditions stated above. However, the library
can be used for any tree. A way to use the library with IDs which do not fullfill the conditions,
it to map them to an ID space which does, and store the original IDs as an attribute.
Besides the IDs, a tree can contain further information, e.g. integers, floats or other
data, here called attributes, associated to the nodes. Each node can contain zero, one or more values
for an attribute. To add values for an attribute, a tabular file or another data
source (a Python function) is selected.
The data for any subtree can then be easily and efficently queried; thereby the node IDs and/other
selected attributes can be retrieved.
The tree representation is dynamic, i.e. both the tree topology and the attribute values can be
edited and changed.
Working with the library
Installation
The package can be installed using pip install fastsubtrees.
Command line interface
The command line tool fastsubtrees allows constructing and modifying a tree
(subcommand tree), adding and editing attributes (subcommand attribute)
and performing a subtree query (subcommand query).
The command line interface is further described in the
CLI manual.
CLI example: working with the NCBI taxonomy tree
The example below uses the fastsubtrees command, as well as the ntdownload library
(installed as a dependency, by pip) for obtaining the NCBI taxonomy data.
ntdownload ntdumps # download NCBI taxonomy data
fastsubtrees tree nt.tree --ncbi ntdumps/nodes.dmp -f # create the tree
fastsubtrees query nt.tree 562 # query node 562

# attributes
ATTRTAB=data/accession_taxid_attribute.tsv.gz # data file
TAXID=2; GENOME_SIZE=3; GC_CONTENT=4 # column numbers, 1-based

fastsubtrees attribute nt.tree genome_size $ATTRTAB -e $TAXID -v $GENOME_SIZE -t int
fastsubtrees attribute nt.tree GC_content $ATTRTAB -e $TAXID -v $GC_CONTENT -t float

fastsubtrees query nt.tree 562 genome_size GC_content # query including attributes

# taxonomy names
ntnames ntdumps >| names.tsv # prepare data from names dump
fastsubtrees attribute nt.tree taxname names.tsv # add names as attribute
fastsubtrees query nt.tree 562 taxname genome_size # query including taxa names

Using NtSubtree
The package ntsubtree (installable by pip) simplifies working with the NCBI taxonomy even more.
Tree and the taxonomic names tables are automatically created and stored in a central location.
# first run after installing automatically downloads and constructs the tree

ntsubtree query 562 # taxonomic names displayed alongside the IDs
ntsubtree query -n "Escherichia" # Query by taxonomic name

# attributes
ATTRTAB=data/accession_taxid_attribute.tsv.gz # data file
TAXID=2; GENOME_SIZE=3; GC_CONTENT=4 # column numbers

ntsubtree attribute genome_size $ATTRTAB -e $TAXID -v $GENOME_SIZE
ntsubtree attribute GC_content $ATTRTAB -e $TAXID -v $GC_CONTENT
ntsubtree query -n "Escherichia" genome_size GC_content

# check if a newer version of the taxonomy data is available
# and update the tree if necessary, keeping the attribute values:
ntsubtree update

API
The library functionality can be also directly accessed in Python code using
the API, which is documented in the
API manual.
API example: working with the NCBI taxonomy tree
The example below uses the fastsubtrees command, as well as the ntdownload library
(installed as a dependency, by pip) for obtaining the NCBI taxonomy data.
# download the NCBI taxonomy data
from ntdownload import Downloader
d = Downloader("ntdumpsdir")
has_downloaded = d.run()

from fastsubtrees import Tree
infile = "ntdumpsdir/nodes.dmp"
tree = Tree.construct_from_ncbi_dump(infile) # create the tree
results = tree.subtree_ids(562) # retrieve subtree IDs

attrtab="data/accession_taxid_attribute.tsv.gz" # data file
taxid_col=1; genome_size_col=2; gc_content_col=3 # column numbers, 0-based

tree.to_file("nt.tree")
tree.create_attribute_from_tabular("genome_size", attrtab, elem_field_num=taxid_col,
attr_field_num=genome_size_col, casting_fn=int)
tree.create_attribute_from_tabular("GC_content", attrtab, elem_field_num=taxid_col,
attr_field_num=gc_content_col, casting_fn=float)
results = tree.subtree_info(562, ["genome_size", "GC_content"])

# taxonomy names
from ntdownload import yield_scientific_names_from_dump as generator
tree.create_attribute("taxname", generator("ntdumpsdir"))
results = tree.subtree_info(562, ["taxname", "genome_size"])

Using NtSubtree
The package ntsubtree (installable by pip) simplifies working with the NCBI taxonomy even more.
Tree and the taxonomic names tables are automatically created and stored in a central location.
The first time the library is included these operations are done automatically.
import ntsubtree

tree = ntsubtree.get_tree()
results = tree.subtree_ids(562)

taxid = ntsubtree.search_name("Escherichia")
results = tree.subtree_info(taxid, ["taxname"])

attrtab="data/accession_taxid_attribute.tsv.gz" # data file
taxid_col=1; genome_size_col=2; gc_content_col=3 # column numbers, 0-based

tree.create_attribute_from_tabular("genome_size", attrtab, elem_field_num=taxid_col,
attr_field_num=genome_size_col, casting_fn=int)
tree.create_attribute_from_tabular("GC_content", attrtab, elem_field_num=taxid_col,
attr_field_num=gc_content_col, casting_fn=float)
results = tree.subtree_info(562, ["genome_size", "GC_content"])

# check if a newer version of the taxonomy data is available
# and update the tree if necessary, keeping the attribute values:
ntsubtree.update()

Docker
To try or test the package, it is possible to use fastsubtrees
by employing the Docker image defined in Dockerfile.
This does not require any external database installation and configuration.

Example of the Docker command line:
# create a Docker image
docker build --tag "fastsubtrees" .

# create a container and run it
docker run -p 8050:8050 --detach --name fastsubtreesC fastsubtrees
# or, if it was already created and stopped, restart it using:
# docker start fastsubtreesC

# run the tests
docker exec fastsubtreesC tests

# run benchmarks
docker exec fastsubtreesC benchmarks

# run the example application
docker exec fastsubtreesC start-example-app
# now open it in the browser at https://0.0.0.0:8050


Tests
To run the test suite, you can use pytest (or make tests).
The tests include tests of fastsubtrees and of the sub-package ntmirror.
The latter are partly dependent on a database installation and configuration
which must be given in ntmirror/tests/config.yaml;
database-dependent tests are skipped if this configuration file is not provided.
The entire test suite can be also run from the Docker container,
without further configuration, see above the Docker section.
Benchmarks
Benchmarks can be run using the shell scripts provided under benchmarks.
These require data, which is downloaded from NCBI taxonomy and
some pre-computed example data which is provided in the data subdirectory
(genome sizes and GC content).
The benchmarks can be convienently run from the Docker container, without
requiring a database installation and setup, see above the Docker section.
Example application: Genome attributes viewer
An interactive web application based on fastsubtrees was developed using
dash. It allows to graphically display the distribution of values of
attributes in subtrees of the NCBI taxonomic tree.
It is a separate Python package, which can
be installed using pip, and depends on fastsubtrees.
It can also be installed using the Docker image of
fastsubtrees (see above in the Docker section).
For more information see also the genomes-attributes-viewer/README.md file.
Local installation and startup
To application can be installed using pip install genomes_attributes_viewer
or from the genomes_attributes_viewer directory of the fastsubtrees
repository.
To start the application, use the genomes-attributes-viewer.
The first time this command is run, the application data are downloaded and
prepared, taking a few seconds. Startup on subsequent
starts does not require these operations and is thus faster.
Other subpackages
NtSubtree
NtSubtree is a library which automatically downloads the NCBI taxonomy
dump and constructs the fastsubtrees data for it. It allows to easily
keep the data up-to-date. It is a separate Python package, which can
be installed using pip, and depends on fastsubtrees.
The query command of the NtSubtree CLI tool automatically
display also taxonomic names, alongside the IDs in query and allow to
perform queries by taxonomic name.
For more information see also the ntsubtree/README.md file.
ntdownload
When working with the NCBI taxonomy database, a local copy of the NCBI taxonomy
dump can be obtained and kept up-to-date using the ntdownload package, which
is located in the directory ntdownload. It is a separate
Python package, which can be installed using pip, independently
from fastsubtrees.
Please refer to the user manual of ntdownload located under ntdownload/README.md
for more information.
ntmirror
A downloaded NCBI taxonomy database dump can be loaded to
a local SQL database, using the package ntmirror, which is located
in the directory ntmirror.
It is a separate Python package, which can
be installed using pip, independently from fastsubtrees.
It contains also a script to extract subtrees
from the local database mirror using hierarchical SQL queries.
Please refer to the user manual of ntmirror located under ntmirror/README.md
for more information.
Internals
For achieving an efficient running time and memory use, the nodes of the tree
are represented compactly in deep-first traversal order.
Subtrees are then extracted in O(s) time, where s is the size of the extracted
subtree (i.e. not depending on the size of the whole tree).
The IDs must not
necessarily be all consecutive (i.e. some "holes" may be present), but the
largest node ID (idmax) should not be much larger than the total number of
nodes, because the memory consumption is in O(idmax).
For each attribute defined in a tree, a file is created, where the attribute
values are stored. The attributes are also stored in the same deep-first traversal
order as the tree IDs.
Tree construction algorithm
The tree construction algorithm used here is the following,
where the input data consists of 2-tuples (element_id, parent_id)
and the maximum node ID m is not much larger than the number of IDs n.

iteration over the input data to construct a table P of parents by ID,
i.e. P[element_id]=parent_id if element_id is in the tree,
and P[element_id]=UNDEF if not, where UNDEF is a special value.
This requires O(n) steps
for reading the IDs and O(m) steps for writing either the ID or the UNDEF
value to P; since m>=n, the total time is in O(m).
iteration over table P to construct a table S of subtree sizes
by ID; for each element the tree is climbed to the root, to add the
element to the counts of each ancestor. This
operation requires O(n*d) time, where d is the height of the node,
which is in average case much lower than m and d=m is the worst case.
iteration over each node ID to construct the list D, consisting of the depth first order of
the nodes, and the table C of the coordinates of all nodes in the tree data, by id.
For this operation, first the root is added to D and C, then
for each other node x in P, the tree is climbed and nodes added to a stack until the next not-yet-added
ancestor is found. The position where to add it this node is computed by the next
free position in the subtree of its parent (which must have been already added,
by definition, thus the next free position in its subtree is known). After this,
the next stack element is added, until x is added.
Although this operation also requires climbing the tree, it takes in total O(n) time,
since each node is added only once.

Parallelizing the tree construction
Currently the slowest step of the construction, detailed in the previous
section, is the second, i.e. the computation of S.
Since each node must be count in the subtree size of all its ancestors,
there is no easy way to reduce the time from O(n*h).
To parallelize this step, one divides the parents table into t slices,
and assign each to a different sub-process (not thread, because of the GIL).
Each sub-process would then count the subtree sizes in the slice only.
A version implemented with a shared table and a lock was too slow,
since access to the table was concurrent among the sub-processes.
In the current version, instead, each sub-process makes a own subtree sizes
S' table. The sub-processes S' tables are summed up after completion for
obtaining the S table.
This option can be activated in the CLI using the --processes P option,
or in the API setting the nprocesses argument of Tree.construct and
related methods. Benchmarks show that the parallel version did not significantly
improve the performance on constructing the NCBI taxonomy tree, likely
because of the overhead of process starting, array S' initialization
and summing up of all S' to S after completion.
Community guidelines
Contributions to the software are welcome. Please clone this repository
and send a pull request on Github, to let the changes be integrated in
the original repository.
In case of bugs and issues, please report them through the Github Issues page
of the repository.
Documentation
The complete documentation of Fastsubtrees is available on ReadTheDocs
at https://fastsubtrees.readthedocs.io/ in website and
PDF format.

License

For personal and professional use. You cannot resell or redistribute these repositories in their original state.

Share

• Share on Facebook
• Share on Twitter