BACKGROUND
in a phylogenetic tree, living organisms occupy the leaves and ancestral organisms are internal nodes, with the edges of the tree denoting evolutionary relationships .
the task of phylogenetics is to infer this tree from observations  obtained from existing organisms of interest.
to reconstruct a phylogenetic tree, the most popular techniques  often return tens to hundreds of thousands of trees that represent equally-plausible or closely-related hypotheses  for how the taxa evolved from a common ancestor.
given that phylogenetic searches return tens to hundreds of thousands of candidate evolutionary trees, biologists need new techniques for managing and sharing these large tree collections effectively.
as biologists obtain more data to produce evolutionary trees, phylogenetic techniques must reconstruct larger trees, resulting in ever-larger collections of candidate trees.
thus, there is a critical need to develop phylogenetic compression techniques that reduce the requirements of storing large tree collections so that they can be shared easily with colleagues around the world.
we introduced treezip  <cit> , a novel compression algorithm that reduces the requirements over standard compression algorithms  for storing and sharing large collections of evolutionary trees.
given that many of the evolutionary relationships in a collection of phylogenetic trees are shared, the novelty of the treezip approach is storing such relationships only once in the compressed representation.
treezip compresses a newick file based on the semantic representation .
the newick format  <cit>  is the most widely used file format to represent phylogenetic trees.
in this format, the topology of the evolutionary tree is represented using a notation based on balanced parentheses .
a newick formatted tree uses nested parentheses to represent the evolutionary relationships  within a phylogenetic tree.
in a newick file, each tree is located individually on separate lines.
figure  <dig> shows two sets of different, but equivalent newick representations for the three trees shown in figure  <dig>  matching pairs of parentheses symbolize internal nodes in the evolutionary tree.
however, the newick representation of a tree is not unique.
for a particular tree with n taxa, there are o different  newick strings to represent its topology.
consequently, general-purpose data compression techniques cannot leverage domain-specific information regarding the newick file.
thus, our treezip approach shows that there is great potential for obtaining good compression by utilizing the semantic information in a newick file of evolutionary trees.
related work
besides treezip, the only other known phylogenetic tree compressor known by us is the texas analysis of symbolic phylogenetic information  algorithm  <cit> .
the benefits of taspi include compressing phylogenetic trees and computing their consensus.
treezip shares these benefits as well as the ability to handle branch lengths, merge tree collections, and extract subsets of trees directly from the compressed treezip file.
also, the authors of taspi state that their approach is not robust to the o different newick representations of a phylogenetic tree.
our experimental results show that treezip's performance is not impacted by these different newick representations.
our contributions
in this paper, we improve upon our treezip algorithm in three significant ways.
first, we extend treezip to handle weighted phylogenetic trees containing branch lengths as shown in figure  <dig>  next, we show the extensibility of the treezip compressed format when given a newick file representing a collection of t trees.
that is, in addition to extracting all of the trees contained in a compressed trz file, we show how the treezip format can be used to perform additional extraction operations  and constructing majority and strict consensus trees.
our final extension shows how we can use set operations  on trz files to merge tree collections.
we experimentally study the performance of our treezip algorithm in comparison to 7zip on four biological data sets, including freshwater , angiosperms , fish  and insects  tree collections.
of these datasets, the first three are weighted , while the last is unweighted.
our largest  tree collection consists of  <dig>   trees requiring  <dig> mb  of storage space.
however, due to the storage requirements of weighted tree collections, our fish dataset consisting of  <dig>  264-taxa trees has the largest file size of  <dig> mb.
overall, our results show that the compressed treezip  file is over 74% smaller than the original newick file on weighted collections.
on unweighted collections, it is 98% smaller.
when treezip is coupled with 7zip, the resulting trz+7zip file is on average 92% smaller on weighted collections.
on unweighted collections, the trz+7zip file is in excess of  <dig> % smaller than the original newick file.
given that there are o different newick representations for a phylogenetic tree, we study the impact of these different, but equivalent representations on both the treezip and 7zip approaches.
the results show that as the number of different newick representations increases, there is a significant increase in 7zip's compressed representation.
treezip, on the other hand, is robust to changes in the newick string representation of a tree.
furthermore, not only does treezip produce a smaller compressed file than 7zip, it often does so in a time that is faster or comparable to 7zip.
beyond decompressing a trz file to its original newick representation, our experiments provide exciting results related to the flexibility of extracting additional information from the compressed file.
of interest to biologists are the unique set of trees that are contained in their tree collection .
moreover, we can output the strict and majority consensus trees from the phylogenetic data in the trz file in less than one second on the tree collections studied in this paper.
since the trz file is text, various set operations can be quickly and efficiently performed on the trz representation of a weighted  collection of trees up to  <dig>  times faster than on the newick representation.
thus, our results show that the trz file is an effective and extensible compressed format that biologists can leverage to manage their large tree collections.
paper structure
the rest of this paper is organized as follows.
in our methods section, we describe the treezip algorithm, including the mechanisms behind compression, decompression, and our set operations functionality.
we also describe our experimental methodology.
we describe and discuss our experimental results in our results and discussion section.
lastly, we summarize our findings in conclusions.
methods
the treezip algorithm is composed of two main parts: compression and decompression.
in the subsections that follow, we first discuss the process of compression, in which a newick input file is transformed into the treezip compressed format, or trz file.
next, we discuss decompression, in which a trz file is used to reconstruct the desired set of phylogenetic trees in newick format.
we note here that since any phylogenetic tree with n taxa has o equivalent newick string representations, any one of these equivalent newick string representations can be used as the decompressed version.
we continue with a description of the algorithm behind the treezip set operations.
unlike the compression and decompression functions, the treezip set operations take as input two trz files, and outputs a single trz file.
in this manner, set operations are performed in the context of a trz file, without any loss of space savings.
lastly, we present a summary of our experimental methodology.
compression
in the newick input file, each string i, which represents tree ti, is read and stored in a tree data structure.
during the depth-first traversal of input tree ti, each of its bipartitions is fed through two universal hash functions, h <dig> and h <dig> <cit> .
there are  <dig> total bipartitions contained in each tree ti, where n is the number of taxa.
thus, each of the 6-taxa trees in figure  <dig> contains  <dig> bipartitions.
both of the universal hashing functions require as input a n-bit bitstring representation of each bipartition in tree ti.
taxa are ordered lexicographically, where b <dig> represents the first bit and the first taxon name in the ordering, b <dig> is the second bit representing the taxon in the ordering, etc.
for the phylogenetic trees shown in figure  <dig>  the taxa ordering is a, b, c, d, e, and f. the bitstring  <dig> represents the bipartition a|bcdef, which corresponds to edge e <dig> in each of the three trees.
in tree t <dig>  edge e <dig> corresponds to the bipartition abc|def or bitstring  <dig>  which is formed by performing an or operation on the bitstrings of its children represented by edges e <dig> and e <dig>  the bipartition def|abc corresponds to the bitstring  <dig>  which has a branch length of  <dig>  denoted by edge e <dig> in tree t <dig>
step 1: storing bipartitions in a hash table
the hash function h <dig> is used to generate the location  for storing a bipartition in the hash table.
h <dig> is responsible for creating a unique and short bipartition identifier  for the bipartition so that the entire n-bit bitstring does not have to be analyzed in order to insert bipartitions into the hash table.
our two universal hash functions are defined as follows:  and .
r =  is a list of random numbers in the range of , and s =  is a list of random integers between .
b =  is a bipartition represented as an n-bit bitstring.
m <dig> represents the number of entries  in the hash table.
m <dig> represents the largest bipartition id  given to a bipartition.
bi represents the ith bit of the n-bit bitstring representation of the bipartition b.
the first three lines of the compressed trz file represent the taxa names, the number of trees in the file, and the number of unique bipartitions.
afterwards, we process each hash table row which will represent a line in the compressed file.
there are three components  to a trz line.
we also note here that bipartitions stored in the trz file are stored in sorted order according to the number of ones they contain.
ties are broken lexicographically.
this guarantees that if two tree collections have equivalent one-to-one corresponding sets of trees, the trz files of the two collections will be identical despite differences in the newick string representations.
below, we describe how treezip encodes each of these components.
step 2: encoding bitstrings
once all of the bipartitions are organized in the hash table, we begin the process of writing the trz compressed file, which is a plain text file.
we run-length encode our bitstrings.
run-length encoding is a form of data compression in which runs of data  are stored as a single data value and count, rather than as the original run.
for the bitstring  <dig> in figure  <dig>  we would have a run-length encoding of 1:2⌴0: <dig>  where each x : y element represents the data value  and the number of repetitions .
the ⌴ character denotes a space.
since bitstrings can either contain runs of 1s or 0s, we introduce two new symbols.
1: is encoded as k, while 0: encoded as l.  hence, we encode the bitstring  <dig> as k2l <dig>  in our experiments, we considered taking every group of  <dig> bits in our bitstring and translating it to an ascii character.
however, we were able to get better compression by using run-length encoding, which showed significant benefits on our biological tree collections consisting of hundreds of taxa.
step 3: identifying and encoding the set of unique tree ids
let  represent the set of evolutionary trees of interest, where .
for a bipartition b,  represents the set of the trees in  that share that bipartition.
is the set of trees that do not share bipartition b. since these sets are complements, their union comprises the set .
to minimize the amount of information present in our trz output, we print out the contents of the smaller of these two sets.
if , then we output .
otherwise,  is outputted.
in our trz file, we denote  and  lines with the '+'and '-' symbol, respectively.
even with use of the smaller of the  or  sets, the list of tree ids can get very large.
this is due to the fact that as t grows large, the number of bytes necessary to store a single id also grows.
we note first that a tree t can be represented as a k-bit bitstring, where k is the number of bipartitions discovered in the collection.
if we feed these k-bit bitstring representations into a slightly modified version of the above hash functions, we can obtain the set of unique trees, u, where |u| = u. this set of unique trees are given the corresponding tree ids of 0…u –  <dig>  and will represent the total set of trees in consideration with any bipartition.
duplicate information is encoded and stored at the end of the trz file.
since the trees are inserted into the hash table in their order of appearance in the newick file, our lists of tree ids will be in increasing order.
as a result, we store the differences between adjacent elements in our tree id list.
these differences are then run-length encoded.
to eliminate the need for spaces between the run-length encoded differences, the first digit of every element is encoded as a character, with 0… <dig> represented by a…j.
consider bitstring  <dig>  which is in row  <dig>  in our hash table shown in figure  <dig> and has an h <dig> value of  <dig>  the  set will be used for this bipartition, and its run-length encoded differences will be  <dig>  which will be encoded as c. given the large number of shared bipartitions in a collection of trees that result from a phylogenetic search, there will be many more unique trees than unique bipartitions.
hence, encoding the differences in the tree ids leverages the sharing among the trees—especially since  <dig> is the most common difference between adjacent elements in the tree id lists.
step 4: encoding branch lengths
the last item to process on a hash line are the branch lengths associated with a unique bipartition.
branch lengths take the form x.y, where x is the integral and y the mantissa.
for this domain, branch lengths tend to be very small .
hence, we use this property to our advantage by only encoding the integral in special cases .
for these special cases, we store the integral separately along with its related tree id.
on the datasets studied here, at least  <dig> % of the branch lengths begin with  <dig>  the mantissa corresponds to a fixed number, k, of digits.
for our tree collections, k =  <dig>  to encode the mantissa, we take two digits at a time  and translate it into a readable ascii character.
for example if we have a value of  <dig> as input, we add  <dig> to create the corresponding extended ascii readable character ä. it is necessary to add  <dig> to any input value since the first  <dig> characters in ascii are non-printable, control characters.
we tried different universal integer encodings   <cit> , but given the range of integers represented by k digits, the various integer encodings did not result in a smaller compressed file.
this is due to the fact that when k =  <dig>  universal codes become less effective than straight binary as the size of the integers themselves increase  <cit> .
furthermore, we achieve better compression by feeding the resulting trz file to a general-purpose compressor such as 7zip.
however, when using variable byte encoding for the branch lengths, 7zip's algorithm could not reduce the file size any further and resulted in a much larger compressed file.
lastly, we note that branch lengths are not compacted like tree ids since the branch lengths originate from an infinite set of real numbers.
tree ids, on the other hand, are drawn from a finite set of t tree ids ranging from  <dig> to t –  <dig>
decompression
the two major steps of the decompression in treezip are decoding the contents in the trz file and rebuilding the collection of t trees.
decoding reconstructs the original hash table information which consists of bipartition bitstrings and the tree ids that contain them.
when the trz file is decoded, each line of the file is processed sequentially.
first, the taxa information is fed into treezip.
next, the number of trees is read.
each bipartition is then read sequentially.
decompression data structures
to assist in bipartition collection, we maintain two data structures m and n, both which are t × k matrices, where k = 2n is the maximum number of bipartitions for a phylogenetic tree.
the length of each matrix corresponds to the number of trees specified in the trz file.
each row i in matrix m corresponds to the bipartitions required to rebuild tree ti.
the corresponding row in matrix n is the list of associated branch lengths.
for example, in figure  <dig>  the bipartition at row  <dig> of our hash table  is shared among all the trees.
it is therefore added to every row in m. to n, we add the value  <dig>  to n <cit> ,  <dig>  to n <cit>  and  <dig>  to n <cit> , signifying that these are the associated branch lengths for the corresponding bipartition in m. on the other hand, the bipartitions  <dig> and  <dig> are contained only in trees t <dig> and t <dig> respectively, and therefore will be added to m <cit>  and m <cit> .
thus, we also add branch lengths  <dig>  and  <dig>  to n <cit>  and n <cit> .
since each bipartition is processed in order in our trz file, we are able to guarantee a one to one correspondence between the values in m and n. we also maintain a separate data structure that stores duplicate tree information to assist in the construction for m and n.
flexible decompression
decoded bitstrings are the basic units for building trees.
once the bitstrings, associated tree ids and branch lengths are decoded, we can build the original trees one by one.
in order to build tree ti, the tree building function receives as input matrix row m which contains the bipartitions encoded as bitstrings for tree ti, and matrix row n which contain the associated branch lengths for each bipartition in m. each of the t trees is built starting from tree t <dig> and ending with tree tt– <dig>  whose bipartitions  are stored in m <cit>   and m , respectively.
the trees are reconstructed in the same order that they were in the original newick file.
however, given o possible newick strings for a tree ti, the newick representation that treezip outputs for tree ti will probably differ from the newick string in the original file.
this is not a problem semantically since the different strings represent the same tree.
to build tree ti, it is initially represented as a star tree on n taxa.
a star tree is an bitstring representation consisting of all 1's.
in the trz file, bipartitions are stored in decreasing order of their bitstrings.
this means the when it is time to rebuild trees, the bipartitions that group together the most taxa appear first.
the bipartition that groups together the fewest taxa appears last in the sorted list of '1' bit counts.
for each bipartition i, a new internal node in tree ti is created using the bitstring in m, and the associated weight is added using the value in n. hence, the taxa indicated by the '1' bits become children of the new internal node.
the above process repeats until all bipartitions are added to tree ti.
the decompressor can also output sub-collections of trees of interest to the user.
for example, if the user was interested in the set of unique trees in the collection , treezip can return this set of trees of interest to the user.
in addition, treezip has built-in functionality to return the strict and majority-rule consensus trees of an encoded collection of trees in a couple of seconds to the user.
the strict and majority-rule consensus trees are especially of interest to biologists, since this is the summary tree structure that commonly appears in publications.
furthermore, these subcollections of trees can be produced directly from the trz file, without a need to decompress the original collection.
in other words, operations can be performed directly on the trz file without requiring a loss of space savings.
this is not the case with standard compression approaches which produce unreadable binary output.
in these cases, the original file must always be fully decompressed in order for any operations to be performed, resulting in zero space savings.
set operations
one of our goals is to show that the trz file represents a viable alternative archive format to the newick file for representing large collections of trees.
if the same set of operations can be performed on a trz file that can be done on a newick file, then we can argue that the two file types are equivalent.
in order to accomplish this goal, we implemented a series of set operations that exploits the textual structure of the trz file to produce sets of trees of semantic interest.
the set operation functions in treezip takes as input two trz files and outputs a single trz file that represents the results of a particular set operation.
here, we implement three set operations in total: union, intersection, and set difference.
the union between two collections of trees is defined as the set of unique trees that exist over both collections.
the intersection between two collections is defined as the set of unique trees that exist in the first collection and the second collection.
the set difference between two collections is defined as the set of unique trees that exist in the first collection and not in the second.
for example, consider the collections stored in files  <dig> and  <dig> in table  <dig>  in this example, each file contains three trees for a total of six trees labeled from  <dig> to  <dig>  trees  <dig> and  <dig> are identical.
all other trees are distinct from each other.
the union between the trees in files  <dig> and  <dig> consists of five trees .
the intersection consists of one tree , and the set difference consists of two trees .
treezip is able to perform these set operations  quickly since the set of unique bipartitions and trees are known and already encoded into the trz file.
treezip then uses this encoded information to create a new trz file with the set of desired trees without needing to rebuild the tree structures.
on the other hand, if one were to attempt to perform these operations on a newick file, the bipartitions from each tree will have to be extracted and the relationships between the set of trees will have to be discovered every single time.
as tree collections grow large, this can pose a significant overhead.
lastly, we stress again that these set operations can all be performed on the input trz files without any loss of space savings.
this is of critical interest, as it shows the viability of using the trz file as an alternative format for storing trees.
with standard compression methods, the resulting binary file must always be decompressed in order for any type of manipulation on the data to be performed.
as a result, these could not be considered as alternative formats to the newick file.
the trz file on the other hand is a viable format because set operations can be performed on it.
furthermore, since there is no loss of space savings, the trz file is a more efficient way of storing collections of trees.
experimental methodology
our implementation of treezip used in the following experiments can be found at http://treezip.googlecode.com.
experiments were conducted on a  <dig>  ghz intel core  <dig> quad-core machine with  <dig> gb of ram running ubuntu linux  <dig> .
treezip is written in c++ and compiled with gcc  <dig> .
<dig> with the - <dig> compiler option.
biological trees
below, we provide a description of the four biological tree collections used in this study.
our tree collections include trees with weighted and unweighted branches.
while more details are provided in the references for our published tree collections, weighted trees were obtained by running a bayesian phylogenetic analysis using mrbayes  <cit> .
the unweighted trees were derived from a maximum parsimony analysis using tnt  <cit> .
for each dataset, the newick tree file contains t trees in the input file.
all of the weighted collections we use for our experiments contain binary trees.
the unweighted insects dataset, however, contains multifurcating  trees.
<dig>  freshwater:  <dig>  weighted trees obtained from an analysis of  <dig> taxa   <cit> .
the size of the newick file for this tree collection is  <dig> mb.
there are  <dig>  unique bipartitions out of  <dig>   <dig>   <dig> total bipartitions.
<dig>  angiosperms:  <dig>  weighted trees obtained from an analysis of a  <dig> taxa   <cit> .
the size of the newick file for this tree collection is  <dig> mb.
there are  <dig>  unique bipartitions out of  <dig>   <dig>   <dig> total bipartitions.
<dig>  fish:  <dig>  weighted trees obtained from an analysis  <dig> fish taxa .
only binary trees are contained in this dataset.
the size of the newick file for this tree collection is  <dig> mb.
there are  <dig>  unique bipartitions out of  <dig>   <dig>   <dig> total bipartitions.
<dig>  insects:  <dig>  unweighted trees obtained from an analysis  <dig> insect taxa  <cit> .
the trees contained in this set are multifurcating.
the size of the newick file for this tree collection is  <dig> mb.
there are  <dig> unique bipartitions out of  <dig>   <dig>   <dig> total bipartitions.
measuring performance
we compare treezip to the 7zip compression algorithm.
in our previous work  <cit> , we found that 7zip is the most effective method for compressing phylogenetic trees amongst the standard compression methods .
we measure the performance of our treezip algorithm in two primary ways: space savings and by using different, but equivalent newick strings.
please note that 7zip here represents a newick file compressed with the 7zip compression scheme.
space savings and running time
we use the space savings measure to evaluate the performance of treezip in comparison to general-purpose compression algorithms.
the space savings s is calculated as .
a higher space savings percentage denotes better compression of the original file.
the goal is to get the level of space savings as close to 100% as possible.
a value of 0% indicates no difference from the uncompressed, original newick file.
we also use running time to calculate how long each algorithm requires to compress and decompress a file.
time is shown in seconds.
different, but equivalent newick representations
as mentioned previously, for any given tree of n taxa, there are o newick string representations associated with it.
since general purpose compression methods such as 7zip compress tree files by looking for redundancy at the newick string level, they are unable to efficiently compress trees when there is a lack of redundancy in the newick string representations.
to illustrate this, we created a different, but equivalent newick file for each dataset.
for a newick file containing t trees, each tree receives a different, but equivalent newick representation.
we note that using different, but equivalent newick representations does not change the size of the resulting newick file.
for example, our fish dataset consisting of  <dig>  trees over  <dig> taxa requires  <dig> mb of storage space.
the newick file containing different, but equivalent newick strings still occupies  <dig> mb of disk space.
RESULTS
in this section, we explore the compression and decompression performance of 7zip, treezip, and treezip+7zip.
our previous results  <cit>  show that 7zip is the best general-purpose compressor in comparison to gzip and bzip.
the treezip+7zip compressed format is the treezip  format which is then fed to 7zip for further compression.
moreover, our previous study showed that treezip outperforms taspi.
since no implementation of taspi is available and since none of the trees we had available that were used in the taspi experiments had branch lengths, we could not compare treezip to taspi in the context of this study.
finally, each point in the plots represents the average performance over three runs.
compression performance
to measure the effects of branch rotations on our datasets, we took each set of trees and gave them a random, but equivalent newick string representation.
we refer to this process as commuting the newick representation.
figure  <dig> shows the performance of the various compression schemes on different, but equivalent newick string representations.
the trz and trz+7zip files did not increase in file size.
7zip took up to  <dig>  times longer on this new file.
figure  <dig> shows the change in space savings of the different compression schemes between the equivalent newick files and the original files.
here, 100% of the newick strings in the file have been commuted.
a value of  <dig> signifies no change in file size.
the space savings achieved by treezip and treezip+7zip does not change, despite the use of different, but equivalent newick strings.
this highlights treezip's robustness to branch rotations.
this is not the case for 7zip.
on our weighted sets , the size of the 7zip compressed file became almost  <dig> times larger.
on the unweighted set , the 7zip compressed file becomes  <dig> times larger.
this is equivalent of an increase of the size of the 7zip compressed newick file from  <dig> kb to  <dig> mb.
decompression performance
set operations performance
next, we evaluate the performance results of set operations on newick files, newick files compressed with 7zip, trz files, and trz files compressed with 7zip.
each of our four datasets consists of r runs of trees.
that is, for the freshwater dataset, two runs of mrbayes was required to generate the  <dig>  trees in the collection.
for the remaining datasets, r =  <dig> for the angiosperms trees, r =  <dig> for the fish trees, and r =  <dig> for the insects trees.
runs are labeled from r0…rr– <dig>
to create a single data sample for the set operation experiments, we randomly create a bitstring b of length r, where a  <dig> in location bi states that trees from run ri should be used in the set operation experiments and a  <dig> means that trees from that run will not be used.
using the bitstring b as a guide, we create a vector s that contains the identities of those runs that will participate in the set operations experiment.
for example, if b =  <dig>  then s <dig>  s <dig> and s <dig> would contain runs r <dig>  r <dig> and r <dig>  respectively.
we randomly generate a set operation  to apply to the trees represented by s <dig> and s <dig>  let u represent the result.
next, we take the result u and apply a random set operation to it using trees from s <dig>  we continue in this manner until |s| –  <dig> set operations have been applied randomly.
the set operations and the order in which they are applied are also recorded.
for each of our four datasets, the above procedure is repeated  <dig> times in order to create  <dig> data samples.
furthermore, for a particular dataset, all set operation experiments applied to the newick, newick+7zip, trz and trz+7zip files use the same  <dig> data samples along with the same ordering of how the set operations are applied to the data.
our plots show the average running times and file sizes over these  <dig> data samples.
CONCLUSIONS
there is a critical need for phylogenetic compression techniques that reduce the space requirements of large tree collections.
in order to reconstruct the true tree, phylogenetic searches can easily return tens of thousands to hundreds of thousands of candidate evolutionary trees for biologists to consider.
to help biologists handle these large collections of trees, we extend our previous treezip algorithm  <cit>  in several significant ways.
first, the treezip algorithm is augmented to allow for the compression of trees with weighted branches.
second, we offer an extensible decompressor which allows for filtering and extraction of sets of trees of interest.
lastly, treezip can perform fast set operations directly on its compressed trz file.
our experimental evaluation of treezip shows that it compresses a newick file into a plain text trz representation that is at least 73% smaller than the original file on weighted trees and over 98% smaller on unweighted trees.
when combined with 7zip, the treezip+7zip file achieves an average space savings of 92% on the weighted case, and a space savings of over 99% on the unweighted case.
our results also show that treezip's performance is robust to different newick representations of the same phylogenetic tree.
the space savings achieved by 7zip, on the other hand, decreases as the number of different newick representations for the same phylogenetic tree increases.
however, treezip's most powerful advantage arises from its flexible compressed file format.
since the trz file is in plain text, we can easily design extensible decompressors that extract the relevant phylogenetic tree information of interest.
in this paper, we illustrate two decompression applications  that can extract information quickly from a trz file.
furthermore, we showed how we can leverage the trz format to design set operations  to merge tree collections of interest.
our study showed that set operations can be performed up to five times faster on a trz file than on a newick file.
furthermore, the set operation results occupy up to 99% less space in a trz file as compared to its newick counterpart.
overall, our results show that treezip can play a vital role in helping biologists manage their large phylogenetic tree collections effectively.
our future work includes augmenting the extensible decompressor with additional applications and optimizing our implementation to improve treezip's running time.
we also plan to explore how to extend treezip for use beyond phylogenetic trees.
authors' contributions
sm designed and implemented the treezip algorithm, performed all of the experiments, and created all of the figures.
tw also designed the treezip algorithm along with its experimental evaluation.
both authors contributed to writing the manuscript and have approved its final contents.
competing interests
the authors declare that they have no competing interests.

 in a phylogenetic tree, living organisms occupy the leaves and ancestral organisms are internal nodes, with the edges of the tree denoting evolutionary relationships. the task of phylogenetics is to infer this tree from observations obtained from existing organisms of interest. to reconstruct a phylogenetic tree, the most popular techniques often return tens to hundreds of thousands of trees that represent equally-plausible or closely-related hypotheses for how the taxa evolved from a common ancestor. given that phylogenetic searches return tens to hundreds of thousands of candidate evolutionary trees, biologists need new techniques for managing and sharing these large tree collections effectively. as biologists obtain more data to produce evolutionary trees, phylogenetic techniques must reconstruct larger trees, resulting in ever-larger collections of candidate trees. thus, there is a critical need to develop phylogenetic compression techniques that reduce the requirements of storing large tree collections so that they can be shared easily with colleagues around the world. we introduced treezip, a novel compression algorithm that reduces the requirements over standard compression algorithms for storing and sharing large collections of evolutionary trees. given that many of the evolutionary relationships in a collection of phylogenetic trees are shared, the novelty of the treezip approach is storing such relationships only once in the compressed representation. treezip compresses a newick file based on the semantic representation. the newick format is the most widely used file format to represent phylogenetic trees. in this format, the topology of the evolutionary tree is represented using a notation based on balanced parentheses. a newick formatted tree uses nested parentheses to represent the evolutionary relationships within a phylogenetic tree. in a newick file, each tree is located individually on separate lines. figure shows two sets of different, but equivalent newick representations for the three trees shown in figure matching pairs of parentheses symbolize internal nodes in the evolutionary tree. however, the newick representation of a tree is not unique. for a particular tree with n taxa, there are o different newick strings to represent its topology. consequently, general-purpose data compression techniques cannot leverage domain-specific information regarding the newick file. thus, our treezip approach shows that there is great potential for obtaining good compression by utilizing the semantic information in a newick file of evolutionary trees. related work besides treezip, the only other known phylogenetic tree compressor known by us is the texas analysis of symbolic phylogenetic information algorithm. the benefits of taspi include compressing phylogenetic trees and computing their consensus. treezip shares these benefits as well as the ability to handle branch lengths, merge tree collections, and extract subsets of trees directly from the compressed treezip file. also, the authors of taspi state that their approach is not robust to the o different newick representations of a phylogenetic tree. our experimental results show that treezip's performance is not impacted by these different newick representations. our contributions in this paper, we improve upon our treezip algorithm in three significant ways. first, we extend treezip to handle weighted phylogenetic trees containing branch lengths as shown in figure next, we show the extensibility of the treezip compressed format when given a newick file representing a collection of t trees. that is, in addition to extracting all of the trees contained in a compressed trz file, we show how the treezip format can be used to perform additional extraction operations and constructing majority and strict consensus trees. our final extension shows how we can use set operations on trz files to merge tree collections. we experimentally study the performance of our treezip algorithm in comparison to 7zip on four biological data sets, including freshwater, angiosperms, fish and insects tree collections. of these datasets, the first three are weighted, while the last is unweighted. our largest tree collection consists of trees requiring mb of storage space. however, due to the storage requirements of weighted tree collections, our fish dataset consisting of 264-taxa trees has the largest file size of mb. overall, our results show that the compressed treezip file is over 74% smaller than the original newick file on weighted collections. on unweighted collections, it is 98% smaller. when treezip is coupled with 7zip, the resulting trz+7zip file is on average 92% smaller on weighted collections. on unweighted collections, the trz+7zip file is in excess of % smaller than the original newick file. given that there are o different newick representations for a phylogenetic tree, we study the impact of these different, but equivalent representations on both the treezip and 7zip approaches. the results show that as the number of different newick representations increases, there is a significant increase in 7zip's compressed representation. treezip, on the other hand, is robust to changes in the newick string representation of a tree. furthermore, not only does treezip produce a smaller compressed file than 7zip, it often does so in a time that is faster or comparable to 7zip. beyond decompressing a trz file to its original newick representation, our experiments provide exciting results related to the flexibility of extracting additional information from the compressed file. of interest to biologists are the unique set of trees that are contained in their tree collection. moreover, we can output the strict and majority consensus trees from the phylogenetic data in the trz file in less than one second on the tree collections studied in this paper. since the trz file is text, various set operations can be quickly and efficiently performed on the trz representation of a weighted collection of trees up to times faster than on the newick representation. thus, our results show that the trz file is an effective and extensible compressed format that biologists can leverage to manage their large tree collections. paper structure the rest of this paper is organized as follows. in our methods section, we describe the treezip algorithm, including the mechanisms behind compression, decompression, and our set operations functionality. we also describe our experimental methodology. we describe and discuss our experimental results in our results and discussion section. lastly, we summarize our findings in conclusions. methods the treezip algorithm is composed of two main parts: compression and decompression. in the subsections that follow, we first discuss the process of compression, in which a newick input file is transformed into the treezip compressed format, or trz file. next, we discuss decompression, in which a trz file is used to reconstruct the desired set of phylogenetic trees in newick format. we note here that since any phylogenetic tree with n taxa has o equivalent newick string representations, any one of these equivalent newick string representations can be used as the decompressed version. we continue with a description of the algorithm behind the treezip set operations. unlike the compression and decompression functions, the treezip set operations take as input two trz files, and outputs a single trz file. in this manner, set operations are performed in the context of a trz file, without any loss of space savings. lastly, we present a summary of our experimental methodology. compression in the newick input file, each string i, which represents tree ti, is read and stored in a tree data structure. during the depth-first traversal of input tree ti, each of its bipartitions is fed through two universal hash functions, h and h. there are total bipartitions contained in each tree ti, where n is the number of taxa. thus, each of the 6-taxa trees in figure contains bipartitions. both of the universal hashing functions require as input a n-bit bitstring representation of each bipartition in tree ti. taxa are ordered lexicographically, where b represents the first bit and the first taxon name in the ordering, b is the second bit representing the taxon in the ordering, etc. for the phylogenetic trees shown in figure the taxa ordering is a, b, c, d, e, and f. the bitstring represents the bipartition a|bcdef, which corresponds to edge e in each of the three trees. in tree t edge e corresponds to the bipartition abc|def or bitstring which is formed by performing an or operation on the bitstrings of its children represented by edges e and e the bipartition def|abc corresponds to the bitstring which has a branch length of denoted by edge e in tree t step 1: storing bipartitions in a hash table the hash function h is used to generate the location for storing a bipartition in the hash table. h is responsible for creating a unique and short bipartition identifier for the bipartition so that the entire n-bit bitstring does not have to be analyzed in order to insert bipartitions into the hash table. our two universal hash functions are defined as follows: and. r = is a list of random numbers in the range of, and s = is a list of random integers between. b = is a bipartition represented as an n-bit bitstring. m represents the number of entries in the hash table. m represents the largest bipartition id given to a bipartition. bi represents the ith bit of the n-bit bitstring representation of the bipartition b. the first three lines of the compressed trz file represent the taxa names, the number of trees in the file, and the number of unique bipartitions. afterwards, we process each hash table row which will represent a line in the compressed file. there are three components to a trz line. we also note here that bipartitions stored in the trz file are stored in sorted order according to the number of ones they contain. ties are broken lexicographically. this guarantees that if two tree collections have equivalent one-to-one corresponding sets of trees, the trz files of the two collections will be identical despite differences in the newick string representations. below, we describe how treezip encodes each of these components. step 2: encoding bitstrings once all of the bipartitions are organized in the hash table, we begin the process of writing the trz compressed file, which is a plain text file. we run-length encode our bitstrings. run-length encoding is a form of data compression in which runs of data are stored as a single data value and count, rather than as the original run. for the bitstring in figure we would have a run-length encoding of 1:2⌴0: where each x: y element represents the data value and the number of repetitions. the ⌴ character denotes a space. since bitstrings can either contain runs of 1s or 0s, we introduce two new symbols. 1: is encoded as k, while 0: encoded as l. hence, we encode the bitstring as k2l in our experiments, we considered taking every group of bits in our bitstring and translating it to an ascii character. however, we were able to get better compression by using run-length encoding, which showed significant benefits on our biological tree collections consisting of hundreds of taxa. step 3: identifying and encoding the set of unique tree ids let represent the set of evolutionary trees of interest, where. for a bipartition b, represents the set of the trees in that share that bipartition. is the set of trees that do not share bipartition b. since these sets are complements, their union comprises the set. to minimize the amount of information present in our trz output, we print out the contents of the smaller of these two sets. if, then we output. otherwise, is outputted. in our trz file, we denote and lines with the'+'and'-' symbol, respectively. even with use of the smaller of the or sets, the list of tree ids can get very large. this is due to the fact that as t grows large, the number of bytes necessary to store a single id also grows. we note first that a tree t can be represented as a k-bit bitstring, where k is the number of bipartitions discovered in the collection. if we feed these k-bit bitstring representations into a slightly modified version of the above hash functions, we can obtain the set of unique trees, u, where |u| = u. this set of unique trees are given the corresponding tree ids of 0…u – and will represent the total set of trees in consideration with any bipartition. duplicate information is encoded and stored at the end of the trz file. since the trees are inserted into the hash table in their order of appearance in the newick file, our lists of tree ids will be in increasing order. as a result, we store the differences between adjacent elements in our tree id list. these differences are then run-length encoded. to eliminate the need for spaces between the run-length encoded differences, the first digit of every element is encoded as a character, with 0… represented by a…j. consider bitstring which is in row in our hash table shown in figure and has an h value of the set will be used for this bipartition, and its run-length encoded differences will be which will be encoded as c. given the large number of shared bipartitions in a collection of trees that result from a phylogenetic search, there will be many more unique trees than unique bipartitions. hence, encoding the differences in the tree ids leverages the sharing among the trees—especially since is the most common difference between adjacent elements in the tree id lists. step 4: encoding branch lengths the last item to process on a hash line are the branch lengths associated with a unique bipartition. branch lengths take the form x.y, where x is the integral and y the mantissa. for this domain, branch lengths tend to be very small. hence, we use this property to our advantage by only encoding the integral in special cases. for these special cases, we store the integral separately along with its related tree id. on the datasets studied here, at least % of the branch lengths begin with the mantissa corresponds to a fixed number, k, of digits. for our tree collections, k = to encode the mantissa, we take two digits at a time and translate it into a readable ascii character. for example if we have a value of as input, we add to create the corresponding extended ascii readable character ä. it is necessary to add to any input value since the first characters in ascii are non-printable, control characters. we tried different universal integer encodings, but given the range of integers represented by k digits, the various integer encodings did not result in a smaller compressed file. this is due to the fact that when k = universal codes become less effective than straight binary as the size of the integers themselves increase. furthermore, we achieve better compression by feeding the resulting trz file to a general-purpose compressor such as 7zip. however, when using variable byte encoding for the branch lengths, 7zip's algorithm could not reduce the file size any further and resulted in a much larger compressed file. lastly, we note that branch lengths are not compacted like tree ids since the branch lengths originate from an infinite set of real numbers. tree ids, on the other hand, are drawn from a finite set of t tree ids ranging from to t – decompression the two major steps of the decompression in treezip are decoding the contents in the trz file and rebuilding the collection of t trees. decoding reconstructs the original hash table information which consists of bipartition bitstrings and the tree ids that contain them. when the trz file is decoded, each line of the file is processed sequentially. first, the taxa information is fed into treezip. next, the number of trees is read. each bipartition is then read sequentially. decompression data structures to assist in bipartition collection, we maintain two data structures m and n, both which are t × k matrices, where k = 2n is the maximum number of bipartitions for a phylogenetic tree. the length of each matrix corresponds to the number of trees specified in the trz file. each row i in matrix m corresponds to the bipartitions required to rebuild tree ti. the corresponding row in matrix n is the list of associated branch lengths. for example, in figure the bipartition at row of our hash table is shared among all the trees. it is therefore added to every row in m. to n, we add the value to n, to n and to n, signifying that these are the associated branch lengths for the corresponding bipartition in m. on the other hand, the bipartitions and are contained only in trees t and t respectively, and therefore will be added to m and m. thus, we also add branch lengths and to n and n. since each bipartition is processed in order in our trz file, we are able to guarantee a one to one correspondence between the values in m and n. we also maintain a separate data structure that stores duplicate tree information to assist in the construction for m and n. flexible decompression decoded bitstrings are the basic units for building trees. once the bitstrings, associated tree ids and branch lengths are decoded, we can build the original trees one by one. in order to build tree ti, the tree building function receives as input matrix row m which contains the bipartitions encoded as bitstrings for tree ti, and matrix row n which contain the associated branch lengths for each bipartition in m. each of the t trees is built starting from tree t and ending with tree tt– whose bipartitions are stored in m and m, respectively. the trees are reconstructed in the same order that they were in the original newick file. however, given o possible newick strings for a tree ti, the newick representation that treezip outputs for tree ti will probably differ from the newick string in the original file. this is not a problem semantically since the different strings represent the same tree. to build tree ti, it is initially represented as a star tree on n taxa. a star tree is an bitstring representation consisting of all 1's. in the trz file, bipartitions are stored in decreasing order of their bitstrings. this means the when it is time to rebuild trees, the bipartitions that group together the most taxa appear first. the bipartition that groups together the fewest taxa appears last in the sorted list of'1' bit counts. for each bipartition i, a new internal node in tree ti is created using the bitstring in m, and the associated weight is added using the value in n. hence, the taxa indicated by the'1' bits become children of the new internal node. the above process repeats until all bipartitions are added to tree ti. the decompressor can also output sub-collections of trees of interest to the user. for example, if the user was interested in the set of unique trees in the collection, treezip can return this set of trees of interest to the user. in addition, treezip has built-in functionality to return the strict and majority-rule consensus trees of an encoded collection of trees in a couple of seconds to the user. the strict and majority-rule consensus trees are especially of interest to biologists, since this is the summary tree structure that commonly appears in publications. furthermore, these subcollections of trees can be produced directly from the trz file, without a need to decompress the original collection. in other words, operations can be performed directly on the trz file without requiring a loss of space savings. this is not the case with standard compression approaches which produce unreadable binary output. in these cases, the original file must always be fully decompressed in order for any operations to be performed, resulting in zero space savings. set operations one of our goals is to show that the trz file represents a viable alternative archive format to the newick file for representing large collections of trees. if the same set of operations can be performed on a trz file that can be done on a newick file, then we can argue that the two file types are equivalent. in order to accomplish this goal, we implemented a series of set operations that exploits the textual structure of the trz file to produce sets of trees of semantic interest. the set operation functions in treezip takes as input two trz files and outputs a single trz file that represents the results of a particular set operation. here, we implement three set operations in total: union, intersection, and set difference. the union between two collections of trees is defined as the set of unique trees that exist over both collections. the intersection between two collections is defined as the set of unique trees that exist in the first collection and the second collection. the set difference between two collections is defined as the set of unique trees that exist in the first collection and not in the second. for example, consider the collections stored in files and in table in this example, each file contains three trees for a total of six trees labeled from to trees and are identical. all other trees are distinct from each other. the union between the trees in files and consists of five trees. the intersection consists of one tree, and the set difference consists of two trees. treezip is able to perform these set operations quickly since the set of unique bipartitions and trees are known and already encoded into the trz file. treezip then uses this encoded information to create a new trz file with the set of desired trees without needing to rebuild the tree structures. on the other hand, if one were to attempt to perform these operations on a newick file, the bipartitions from each tree will have to be extracted and the relationships between the set of trees will have to be discovered every single time. as tree collections grow large, this can pose a significant overhead. lastly, we stress again that these set operations can all be performed on the input trz files without any loss of space savings. this is of critical interest, as it shows the viability of using the trz file as an alternative format for storing trees. with standard compression methods, the resulting binary file must always be decompressed in order for any type of manipulation on the data to be performed. as a result, these could not be considered as alternative formats to the newick file. the trz file on the other hand is a viable format because set operations can be performed on it. furthermore, since there is no loss of space savings, the trz file is a more efficient way of storing collections of trees. experimental methodology our implementation of treezip used in the following experiments can be found at http://treezip.googlecode.com. experiments were conducted on a ghz intel core quad-core machine with gb of ram running ubuntu linux. treezip is written in c++ and compiled with gcc. with the - compiler option. biological trees below, we provide a description of the four biological tree collections used in this study. our tree collections include trees with weighted and unweighted branches. while more details are provided in the references for our published tree collections, weighted trees were obtained by running a bayesian phylogenetic analysis using mrbayes. the unweighted trees were derived from a maximum parsimony analysis using tnt. for each dataset, the newick tree file contains t trees in the input file. all of the weighted collections we use for our experiments contain binary trees. the unweighted insects dataset, however, contains multifurcating trees. freshwater: weighted trees obtained from an analysis of taxa. the size of the newick file for this tree collection is mb. there are unique bipartitions out of total bipartitions. angiosperms: weighted trees obtained from an analysis of a taxa. the size of the newick file for this tree collection is mb. there are unique bipartitions out of total bipartitions. fish: weighted trees obtained from an analysis fish taxa. only binary trees are contained in this dataset. the size of the newick file for this tree collection is mb. there are unique bipartitions out of total bipartitions. insects: unweighted trees obtained from an analysis insect taxa. the trees contained in this set are multifurcating. the size of the newick file for this tree collection is mb. there are unique bipartitions out of total bipartitions. measuring performance we compare treezip to the 7zip compression algorithm. in our previous work, we found that 7zip is the most effective method for compressing phylogenetic trees amongst the standard compression methods. we measure the performance of our treezip algorithm in two primary ways: space savings and by using different, but equivalent newick strings. please note that 7zip here represents a newick file compressed with the 7zip compression scheme. space savings and running time we use the space savings measure to evaluate the performance of treezip in comparison to general-purpose compression algorithms. the space savings s is calculated as. a higher space savings percentage denotes better compression of the original file. the goal is to get the level of space savings as close to 100% as possible. a value of 0% indicates no difference from the uncompressed, original newick file. we also use running time to calculate how long each algorithm requires to compress and decompress a file. time is shown in seconds. different, but equivalent newick representations as mentioned previously, for any given tree of n taxa, there are o newick string representations associated with it. since general purpose compression methods such as 7zip compress tree files by looking for redundancy at the newick string level, they are unable to efficiently compress trees when there is a lack of redundancy in the newick string representations. to illustrate this, we created a different, but equivalent newick file for each dataset. for a newick file containing t trees, each tree receives a different, but equivalent newick representation. we note that using different, but equivalent newick representations does not change the size of the resulting newick file. for example, our fish dataset consisting of trees over taxa requires mb of storage space. the newick file containing different, but equivalent newick strings still occupies mb of disk space.  in this section, we explore the compression and decompression performance of 7zip, treezip, and treezip+7zip. our previous results show that 7zip is the best general-purpose compressor in comparison to gzip and bzip. the treezip+7zip compressed format is the treezip format which is then fed to 7zip for further compression. moreover, our previous study showed that treezip outperforms taspi. since no implementation of taspi is available and since none of the trees we had available that were used in the taspi experiments had branch lengths, we could not compare treezip to taspi in the context of this study. finally, each point in the plots represents the average performance over three runs. compression performance to measure the effects of branch rotations on our datasets, we took each set of trees and gave them a random, but equivalent newick string representation. we refer to this process as commuting the newick representation. figure shows the performance of the various compression schemes on different, but equivalent newick string representations. the trz and trz+7zip files did not increase in file size. 7zip took up to times longer on this new file. figure shows the change in space savings of the different compression schemes between the equivalent newick files and the original files. here, 100% of the newick strings in the file have been commuted. a value of signifies no change in file size. the space savings achieved by treezip and treezip+7zip does not change, despite the use of different, but equivalent newick strings. this highlights treezip's robustness to branch rotations. this is not the case for 7zip. on our weighted sets, the size of the 7zip compressed file became almost times larger. on the unweighted set, the 7zip compressed file becomes times larger. this is equivalent of an increase of the size of the 7zip compressed newick file from kb to mb. decompression performance set operations performance next, we evaluate the performance results of set operations on newick files, newick files compressed with 7zip, trz files, and trz files compressed with 7zip. each of our four datasets consists of r runs of trees. that is, for the freshwater dataset, two runs of mrbayes was required to generate the trees in the collection. for the remaining datasets, r = for the angiosperms trees, r = for the fish trees, and r = for the insects trees. runs are labeled from r0…rr– to create a single data sample for the set operation experiments, we randomly create a bitstring b of length r, where a in location bi states that trees from run ri should be used in the set operation experiments and a means that trees from that run will not be used. using the bitstring b as a guide, we create a vector s that contains the identities of those runs that will participate in the set operations experiment. for example, if b = then s s and s would contain runs r r and r respectively. we randomly generate a set operation to apply to the trees represented by s and s let u represent the result. next, we take the result u and apply a random set operation to it using trees from s we continue in this manner until |s| – set operations have been applied randomly. the set operations and the order in which they are applied are also recorded. for each of our four datasets, the above procedure is repeated times in order to create data samples. furthermore, for a particular dataset, all set operation experiments applied to the newick, newick+7zip, trz and trz+7zip files use the same data samples along with the same ordering of how the set operations are applied to the data. our plots show the average running times and file sizes over these data samples.  there is a critical need for phylogenetic compression techniques that reduce the space requirements of large tree collections. in order to reconstruct the true tree, phylogenetic searches can easily return tens of thousands to hundreds of thousands of candidate evolutionary trees for biologists to consider. to help biologists handle these large collections of trees, we extend our previous treezip algorithm in several significant ways. first, the treezip algorithm is augmented to allow for the compression of trees with weighted branches. second, we offer an extensible decompressor which allows for filtering and extraction of sets of trees of interest. lastly, treezip can perform fast set operations directly on its compressed trz file. our experimental evaluation of treezip shows that it compresses a newick file into a plain text trz representation that is at least 73% smaller than the original file on weighted trees and over 98% smaller on unweighted trees. when combined with 7zip, the treezip+7zip file achieves an average space savings of 92% on the weighted case, and a space savings of over 99% on the unweighted case. our results also show that treezip's performance is robust to different newick representations of the same phylogenetic tree. the space savings achieved by 7zip, on the other hand, decreases as the number of different newick representations for the same phylogenetic tree increases. however, treezip's most powerful advantage arises from its flexible compressed file format. since the trz file is in plain text, we can easily design extensible decompressors that extract the relevant phylogenetic tree information of interest. in this paper, we illustrate two decompression applications that can extract information quickly from a trz file. furthermore, we showed how we can leverage the trz format to design set operations to merge tree collections of interest. our study showed that set operations can be performed up to five times faster on a trz file than on a newick file. furthermore, the set operation results occupy up to 99% less space in a trz file as compared to its newick counterpart. overall, our results show that treezip can play a vital role in helping biologists manage their large phylogenetic tree collections effectively. our future work includes augmenting the extensible decompressor with additional applications and optimizing our implementation to improve treezip's running time. we also plan to explore how to extend treezip for use beyond phylogenetic trees. authors' contributions sm designed and implemented the treezip algorithm, performed all of the experiments, and created all of the figures. tw also designed the treezip algorithm along with its experimental evaluation. both authors contributed to writing the manuscript and have approved its final contents. competing interests the authors declare that they have no competing interests. 
furthermore, by using the compressed treezip file as input, we have designed an extensible decompressor that can extract subcollections of trees, compute majority and strict consensus trees, and merge tree collections using set operations such as union, intersection, and set difference. on unweighted phylogenetic trees, treezip is able to compress newick files in excess of 98%. on weighted phylogenetic trees, treezip is able to compress a newick file by at least 73%. we also show the ease of which set operations can be performed on trz files, at speeds quicker than those performed on newick or 7zip compressed newick files, and without loss of space savings. the semantic and compact nature of the trz file allow it to be operated upon directly and quickly, without a need to decompress the original newick file. treezip can be combined with 7zip with little overhead, allowing space savings in excess of 99% and 92%. biologists require new algorithms to efficiently compress and store their large collections of phylogenetic trees. our previous work showed that treezip is a promising approach for compressing phylogenetic trees. treezip is an efficient approach for compressing large collections of phylogenetic trees. finally, since the treezip compressed text file contains all the semantic information in a collection of trees, we can easily filter and decompress a subset of trees of interest, or build the resulting consensus tree in a matter of seconds. in this paper, we extend our treezip algorithm by handling trees with weighted branches.
 biologists require new algorithms to efficiently compress and store their large collections of phylogenetic trees. our previous work showed that treezip is a promising approach for compressing phylogenetic trees. in this paper, we extend our treezip algorithm by handling trees with weighted branches. furthermore, by using the compressed treezip file as input, we have designed an extensible decompressor that can extract subcollections of trees, compute majority and strict consensus trees, and merge tree collections using set operations such as union, intersection, and set difference.  on unweighted phylogenetic trees, treezip is able to compress newick files in excess of 98%. on weighted phylogenetic trees, treezip is able to compress a newick file by at least 73%. treezip can be combined with 7zip with little overhead, allowing space savings in excess of 99% and 92%. unlike treezip, 7zip is not immune to branch rotations, and performs worse as the level of variability in the newick string representation increases. finally, since the treezip compressed text file contains all the semantic information in a collection of trees, we can easily filter and decompress a subset of trees of interest, or build the resulting consensus tree in a matter of seconds. we also show the ease of which set operations can be performed on trz files, at speeds quicker than those performed on newick or 7zip compressed newick files, and without loss of space savings.  treezip is an efficient approach for compressing large collections of phylogenetic trees. the semantic and compact nature of the trz file allow it to be operated upon directly and quickly, without a need to decompress the original newick file. we believe that treezip will be vital for compressing and archiving trees in the biological community. 1- april eighth annual mcbios conference. computational biology and bioinformatics for a new decade college station, tx, usa 