in pursuit of large - scale evolutionary questions , biologists are increasingly using massive phylogenetic datasets to reconstruct evergrowing portions of the tree of life .
these large phylogenetic trees are commonly inferred using a supermatrix approach , in which multiple datasets are combined and analyzed simultaneously.1 however , assembling and utilizing supermatrices is challenging due to difficulties such as determining homology of molecular sequences , assembling chimeric operational taxonomic units , and managing the amount of missing data . despite these challenges ,
the phylota browser2 provides a web interface to view all genbank sequences within taxonomic groups clustered into homologs .
a different approach is implemented in the programs , such as phlawd3 and ncbiminer,4 which mine genbank for sequence clusters homologous to guide sequences provided by the user .
the method implemented in supermatrix constructor ( sumac ) combines elements of both approaches ; the user can perform an exploratory clustering of all genbank sequences within a taxonomic group or provide guide sequences to build homologous sequence clusters in a more targeted manner . furthermore , by calculating supermatrix assessment metrics derived from the concept of phylogenetic decisiveness,5 sumac provides a unique toolkit with which genbank can be repeatedly mined using different settings and the resulting data matrices can be compared . in this article ,
my objectives are to ( 1 ) introduce the sumac software , ( 2 ) describe a novel metric that assesses the effect of missing data in phylogenetic supermatrices , and ( 3 ) illustrate the use of sumac with a case study .
sumac is a python package designed to run as a stand - alone command - line program , though the modules can also be imported and used in other python scripts . when run from the command line
first , sumac creates a local sqlite36 database of the specified genbank division ( eg , pln or mam ) , automatically downloading sequences from ncbi if necessary . using ncbi taxonomy , sumac searches the local database for all sequences in the user - specified ingroup and outgroup .
found sequences are then clustered as putative homologs in one of the two ways : ( 1 ) performing exhaustive all - by - all blastn7 comparisons of each ingroup and outgroup sequence and using a single - linkage hierarchical clustering algorithm or ( 2 ) user - provided guide sequences that typify each cluster are blasted against all ingroup and outgroup sequences . by default ,
this achieves o(n ) time complexity by representing the dendrogram of hierarchical sequence clusters in pointer representation .
given n sequences and the dendrogram c , pointer representation consists of two functions : 
 (i)=max{j:(i , j)c((i))i , j[0,n1]}(i)=inf{h:j > i(i , j)c(h)i , j[0,n1 ] } the function (i ) is the last sequence that sequence i clusters with , and (i ) is the distance h ( the blast e - value ) between sequence (i ) and sequence i. sumac s default clustering depth is an e - value threshold of 1.0e10 and a sequence length percent similarity threshold of 0.5 , although both thresholds can be modified by the user with optional command - line arguments . if run with the command - line flag hac , sumac will instead cluster sequences using a naive hierarchical agglomerative clustering ( hac ) algorithm . proposed by sneath,9
this single - linkage clustering algorithm uses an agglomerative scheme that merges the closest sequence clusters into consecutively larger clusters .
however , with o(n ) time complexity , the hac algorithm is considerably less efficient than the slink algorithm .
once clustering is complete , sumac discards clusters that are not phylogenetically informative ( < 4 taxa ) , and aligns each cluster of sequences using mafft10 with the adjustdirection flag to ensure correct sequence polarity .
the individual locus alignments are saved to enable gene tree inference , and then the alignments are concatenated by species binomial ( based on the ncbi taxonomy ) to create the final supermatrix
. finally , a number of metrics are reported , a graph indicating taxon coverage density is generated , and spreadsheets ( in comma - separated values [ csv ] format ) are produced with the information about each dna region and genbank accession used in the supermatrix .
sumac utilizes python s multiprocessing module11 to parallelize blast comparisons and mafft alignments on multicore computer systems .
when run with the decisiveness command - line flag , sumac will calculate the fraction of triples , a metric of the partial decisiveness ( pd ) of the sequence matrix.13 pd measures how the arrangement of missing data in a multilocus sequence matrix limits the number of trees out of all possible trees that can be inferred .
the fraction of triples is the easiest pd metric to compute and applies to the set of all rooted trees ; it is the percentage of each possible set of three taxa , which all have sequence data for at least one of the same gene regions .
here , i extend the fraction of triples to calculate missing sequence decisiveness scores ( msds ) , which measures the contribution of each individual missing sequence to the overall pd of the matrix .
msds values are in the range [ 0 , 1 ] and are only assigned to missing sequences .
when the msds of a missing sequence is close to 1 , the addition of new data will increase the pd of the matrix more than where msds is low . in this way ,
msds prioritizes which sequences to add to the matrix and identifies taxa or loci that contribute disproportionately to the lack of decisiveness in the matrix .
sumac produces a graph that portrays the distribution of msds across the supermatrix ( fig .
pd metrics and msds can be applied to any multilocus phylogenetic matrix , thus sumac can calculate these metrics for user - provided sequence alignments as well as those mined by sumac from genbank .
given a set x of n taxa and a collection s = { y1 ,  , yk } of subsets of x with an overall fraction of triples  , the msds mij of taxon i and locus j is 
 mij=(imin{l : lx}max{m : mx}min{l : lx}+jmin{s : ss}max{t : ts}min{s : ss})/2,wherei=i,j=j .
i is the fraction of triples of s with taxon i removed , and j is the fraction of triples of s with locus j removed . for the case
the calculations above are performed after substituting values for  , i for all i  x and j for all j  s , which are computed using a modified version of fischer s phylogenetic decisiveness decision problem algorithm for rooted trees.14 this algorithm has an o(k  n ) time complexity .
to demonstrate the utility of sumac for discovering phylogenetically informative sequences within genbank , i compared the construction of a phylogenetic supermatrix using both the phylota browser2 and sumac .
i did not use phlawd3 or ncbiminer4 since they only target genes already known to be of interest .
the goal of this example was to build a supermatrix of the plant families onagraceae ( as an ingroup ) and lythraceae ( as an outgroup ) with as many informative loci as possible .
i searched the phylota database for the taxon names onagraceae and lythraceae , retrieving 5504 and 2547sequences , respectively .
phylota constructed supermatrics for each of the two groups separately , resulting in an onagraceae supermatrix with 325 species and 43 phylogenetically informative sequence clusters .
many of the sequence clusters should have been combined ; for example , 8 of the 43 onagraceae clusters were fragments of the 18s ribosomal gene . to use these data for a phylogenetic analysis
, the 120 onagraceae and lythraceae clusters would need to be reviewed and manually combined .
i ran sumac with the command python -m sumac -d pln -i onagraceae -o lythraceae .
sumac found 846 more sequences than phylota because sumac always uses the latest available release of genbank ( release 205 in this case ) , whereas phylota was developed using genbank release 194 .
sumac constructed an initial supermatrix of 599 onagraceae and lythraceae species consisting of 108 phylogenetically informative sequence clusters .
similar to the results from phylota , some of the 108 sequence clusters should have been combined ( again eight of the clusters were fragments of 18s ribosomal dna ) . with sumac , however , the user has options to produce a more satisfactory data matrix .
one option is to repeat the data - mining process using less stringent thresholds for clustering .
these can be configured by the user with the e - value and length flags .
another option , and the one demonstrated here , is to select sequences from the recovered clusters to act as guide sequences and build homologous clusters in a targeted manner similar to the approach used in phlawd .
of the 108 sequence clusters , i selected guide sequences from the 10 clusters with the highest taxon coverage .
sumac was then run a second time using the guide flag to produce a final supermatrix of 10 gene regions and 384 species ( fig .
the final taxon coverage density was 0.26 and the pd was 0.31 . if necessary , this last step could be repeated using different gene regions to try to increase the decisiveness of the sequence matrix .
furthermore , sumac prioritized the acquisition of new sequence data by calculating msds for each missing sequence ( table 1 ) .
the advantage of the supermatrix approach to phylogenetic estimation is that it combines data from diverse sources into one large analysis .
using guide sequences makes supermatrix construction much faster ; however , it requires a priori knowledge of which dna regions will be used in the supermatrix .
performing all - by - all blast comparisons is computationally more expensive , but it effectively data - mines genbank in an exploratory fashion , so that sequence data not necessarily used in previous systematic studies can also be incorporated into the supermatrix .
sumac enables both options to be pursued and provides metrics to compare the resulting supermatrices .
additionally , genbank can be repeatedly mined using different clustering threshold values to optimize the resulting sequence matrix for the taxonomic group being analyzed and the sequence data available .
msds quantifies the distribution of phylogenetic pd over a given multilocus sequence matrix ( fig .
multiple properties of msds are worth exploring in an expanded simulation study . for example , sequences could be selectively removed from a complete dataset to examine how msds is related to phylogenetic uncertainty during tree inference .
msds could be mapped onto the branches of phylogenies to determine the impact missing data have on the posterior probabilities and/or bootstrap values of clades . with methodological refinements such as those presented here
, supermatrix methods will continue to be widely used for large - scale phylogenetic studies .
however , alternative approaches such as supertrees15 and coalescent - based gene tree / species tree methods16 are increasingly used .
sumac outputs both a concatenated supermatrix and individual gene alignments , enabling the application of multiple phylogenetic inference methods .
many of the methodological advances developed for supermatrix approaches apply equally well to gene tree / species tree approaches , thus utilities such as sumac will continue to be indispensable as researchers aggregate increasingly large phylogenetic datasets and assess the effect of missing data .
 the amount of phylogenetically informative sequence data in genbank is growing at an exponential rate , and large phylogenetic trees are increasingly used in research . 
 tools are needed to construct phylogenetic sequence matrices from genbank data and evaluate the effect of missing data . 
 supermatrix constructor ( sumac ) is a tool to data - mine genbank , construct phylogenetic supermatrices , and assess the phylogenetic decisiveness of a matrix given the pattern of missing sequence data . 
 sumac calculates a novel metric , missing sequence decisiveness scores ( msds ) , which measures how much each individual missing sequence contributes to the decisiveness of the matrix . 
 msds can be used to compare supermatrices and prioritize the acquisition of new sequence data . 
 sumac constructs supermatrices either through an exploratory clustering of all genbank sequences within a taxonomic group or by using guide sequences to build homologous clusters in a more targeted manner . 
 sumac assembles supermatrices for any taxonomic group recognized in genbank and is optimized to run on multicore computer systems by parallelizing multiple stages of operation . 
 sumac is implemented as a python package that can run as a stand - alone command - line program , or its modules and objects can be incorporated within other programs . 
 sumac is released under the open source gplv3 license and is available at https://github.com/wf8/sumac . 
Introduction
Implementation
Missing Sequence Decisiveness Scores
Case Study
Discussion