STELAR-X: Scaling Coalescent-Based Species Tree Inference to 100,000 Species and Beyond

STELAR-X: Scaling Coalescent-Based Species Tree Inference to 100,000 Species and Beyond | bioRxiv /* */ /* */ <!-- <!-- /*! * yepnope1.5.4 * (c) WTFPL, GPLv2 */ (function(a,b,c){function d(a){return"[object Function]"==o.call(a)}function e(a){return"string"==typeof a}function f(){}function g(a){return!a||"loaded"==a||"complete"==a||"uninitialized"==a}function h(){var a=p.shift();q=1,a?a.t?m(function(){("c"==a.t?B.injectCss:B.injectJs)(a.s,0,a.a,a.x,a.e,1)},0):(a(),h()):q=0}function i(a,c,d,e,f,i,j){function k(b){if(!o&&g(l.readyState)&&(u.r=o=1,!q&&h(),l.onload=l.onreadystatechange=null,b)){"img"!=a&&m(function(){t.removeChild(l)},50);for(var d in y[c])y[c].hasOwnProperty(d)&&y[c][d].onload()}}var j=j||B.errorTimeout,l=b.createElement(a),o=0,r=0,u={t:d,s:c,e:f,a:i,x:j};1===y[c]&&(r=1,y[c]=[]),"object"==a?l.data=c:(l.src=c,l.type=a),l.width=l.height="0",l.onerror=l.onload=l.onreadystatechange=function(){k.call(this,r)},p.splice(e,0,u),"img"!=a&&(r||2===y[c]?(t.insertBefore(l,s?null:n),m(k,j)):y[c].push(l))}function j(a,b,c,d,f){return q=0,b=b||"j",e(a)?i("c"==b?v:u,a,b,this.i++,c,d,f):(p.splice(this.i++,0,a),1==p.length&&h()),this}function k(){var a=B;return a.loader={load:j,i:0},a}var l=b.documentElement,m=a.setTimeout,n=b.getElementsByTagName("script")[0],o={}.toString,p=[],q=0,r="MozAppearance"in l.style,s=r&&!!b.createRange().compareNode,t=s?l:n.parentNode,l=a.opera&&"[object Opera]"==o.call(a.opera),l=!!b.attachEvent&&!l,u=r?"object":l?"script":"img",v=l?"script":u,w=Array.isArray||function(a){return"[object Array]"==o.call(a)},x=[],y={},z={timeout:function(a,b){return b.length&&(a.timeout=b[0]),a}},A,B;B=function(a){function b(a){var a=a.split("!"),b=x.length,c=a.pop(),d=a.length,c={url:c,origUrl:c,prefixes:a},e,f,g;for(f=0;f<d;f++)g=a[f].split("="),(e=z[g.shift()])&&(c=e(c,g));for(f=0;f<b;f++)c=x[f](c);return c}function g(a,e,f,g,h){var i=b(a),j=i.autoCallback;i.url.split(".").pop().split("?").shift(),i.bypass||(e&&(e=d(e)?e:e[a]||e[g]||e[a.split("/").pop().split("?")[0]]),i.instead?i.instead(a,e,f,g,h):(y[i.url]?i.noexec=!0:y[i.url]=1,f.load(i.url,i.forceCSS||!i.forceJS&&"css"==i.url.split(".").pop().split("?").shift()?"c":c,i.noexec,i.attrs,i.timeout),(d(e)||d(j))&&f.load(function(){k(),e&&e(i.origUrl,h,g),j&&j(i.origUrl,h,g),y[i.url]=2})))}function h(a,b){function c(a,c){if(a){if(e(a))c||(j=function(){var a=[].slice.call(arguments);k.apply(this,a),l()}),g(a,j,b,0,h);else if(Object(a)===a)for(n in m=function(){var b=0,c;for(c in a)a.hasOwnProperty(c)&&b++;return b}(),a)a.hasOwnProperty(n)&&(!c&&!--m&&(d(j)?j=function(){var a=[].slice.call(arguments);k.apply(this,a),l()}:j[n]=function(a){return function(){var b=[].slice.call(arguments);a&&a.apply(this,b),l()}}(k[n])),g(a[n],j,b,n,h))}else!c&&l()}var h=!!a.test,i=a.load||a.both,j=a.callback||f,k=j,l=a.complete||f,m,n;c(h?a.yep:a.nope,!!i),i&&c(i)}var i,j,l=this.yepnope.loader;if(e(a))g(a,0,l,0);else if(w(a))for(i=0;i (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0];var j=d.createElement(s);var dl=l!='dataLayer'?'&l='+l:'';j.src='//www.googletagmanager.com/gtm.js?id='+i+dl;j.type='text/javascript';j.async=true;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-M677548'); Skip to main content Home About Submit ALERTS / RSS Search for this keyword Advanced Search New Results STELAR-X: Scaling Coalescent-Based Species Tree Inference to 100,000 Species and Beyond View ORCID Profile Anik Saha , Md. Shamsuzzoha Bayzid doi: https://doi.org/10.1101/2025.11.22.689894 Anik Saha 1 Department of Computer Science and Engineering Bangladesh University of Engineering and Technology , Dhaka-1205, Bangladesh Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Anik Saha Md. Shamsuzzoha Bayzid 1 Department of Computer Science and Engineering Bangladesh University of Engineering and Technology , Dhaka-1205, Bangladesh Find this author on Google Scholar Find this author on PubMed Search for this author on this site For correspondence: shams_bayzid{at}cse.buet.ac.bd Abstract Full Text Info/History Metrics Preview PDF Abstract Summary methods reconstruct species trees from collections of gene trees by accounting for gene tree discordance, and offer a statistically consistent framework for phylogenomic inference under the multispecies coalescent model. While existing triplet- and quartet-based approaches such as ASTRAL and STELAR have provable statistical consistency, their running time and memory usage restrict their applicability to ultra-large datasets. We introduce STELAR-X, a statistically consistent and highly scalable triplet-based phylogenetic inference algorithm that achieves an asymptotically optimal memory complexity of O ( nk ) for n species and k gene trees–essentially matching the input size and allowing analyses to remain feasible as long as the input trees fit in memory–while also substantially reducing running time. STELAR-X achieves this by a comprehensive re-engineering of the underlying data structures and algorithms. We introduce a novel, compact integer tuple-based encoding of tree bipartitions and efficient procedures for rapid pre-computation of bipartition weights. We further leverage GPU parallelism for fast pre-computation of necessary weights. This improved and redesigned computational framework underpins a dynamic programming algorithm with substantially reduced computational overhead. Extensive experiments demonstrate that STELAR-X achieves unprecedented scalability. On simulated datasets with 10,000 taxa and 1,000 gene trees, STELAR-X runs 712× faster than ASTRAL-MP (the most scalable variant of ASTRAL) while using 7.5× less CPU memory. Most significantly, STELAR-X analyzed a dataset of 100,000 taxa and 1,000 genes in 8.5 hours using 86 GB RAM, and a 100,000-gene dataset with 1000 taxa in just 4 minutes using 106 GB RAM – scales that were previously intractable for statistically consistent summary methods. STELAR-X is publicly available at https://github.com/aaniksahaa/STELAR-X . 1 Introduction Widespread genome-wide discordance poses a major challenge for phylogenomic studies based on multi-locus datasets [ 1 , 2 ]. A species tree represents the branching pattern of species through speciation events, while a gene tree describes the evolutionary history of a particular gene across those species. Various biological processes can cause different loci to follow different evolutionary paths, so estimating a species tree typically involves analyzing multiple genes and alignments across the genome. Among these processes, incomplete lineage sorting (ILS) is widely recognized as a dominant source of discordance, best explained under the multispecies coalescent model [ 3 – 6 ]. In the presence of gene tree heterogeneity, traditional approaches such as concatenation–where gene alignments are merged into a single supermatrix to infer one tree–can be statistically inconsistent [ 7 , 8 ], and produce incorrect trees with high support [ 9 ]. To overcome these limitations, a range of methods have been developed that explicitly account for ILS, many of which are provably statistically consistent, meaning that they will converge in probability to the true species tree given sufficiently large numbers of genes and sites per gene [ 10 – 14 ]. The most scalable among these are “summary methods”, which first infer gene trees for individual loci and then combine them to estimate the species tree. Notable examples of statistically consistent, coalescent-based summary methods include MP-EST [ 14 ], ASTRAL [ 15 ], BUCKy [ 16 ], GLASS [ 17 ], STEM [ 18 ], SVDquartet [ 13 ], STEAC [ 19 ], NJst [ 20 ], ASTRID [ 21 ], STELAR [ 22 ]. Among summary methods, ASTRAL has emerged as the most widely used and accurate approach for large-scale phylogenomic analyses under the multispecies coalescent model. By maximizing quartet consistency across input gene trees, ASTRAL provides statistically consistent species tree estimates. ASTRAL and its parallel implementation ASTRAL-MP [ 23 ] have been shown to scale to datasets with up to ∼10,000 species with several days of running time. Despite these advances, both ASTRAL and ASTRAL-MP face scalability bottlenecks when the number of species and genes exceeds several tens of thousands. Improving the scalability of species tree inference has long been a key focus in phylogenomics. Divide-and-conquer strategies have proven particularly effective in extending summary methods to larger datasets. For example, the disk-covering method [ 24 ] demonstrated that partitioning taxa into over-lapping subsets (“disks”), inferring local trees, and merging them can substantially enhance scalability of summary methods without sacrificing accuracy. A notable recent development in this direction is uDANCE [ 25 ], a divide-and-conquer framework for inferring and incrementally updating large genome-wide phylogenetic trees. Unlike traditional phylogenomic methods that reconstruct trees de novo each time, uDance can update and expand an existing “backbone” tree as new genomes are added. The backbone-growth paradigm allows uDANCE to analyze much larger taxon sets than standard summary methods. However, constructing a “tree of life” may require building backbone trees consisting of hundreds of thousands of taxa–a challenge that remains unresolved. Furthermore, because uDANCE is not explicitly designed to ensure statistical consistency under the multispecies coalescent model, the scalability of provably consistent summary methods (e.g., ASTRAL) still falls far short of the needs of ultra-large phylogenomics involving hundreds of thousands of species. In this work, we address this gap by introducing STELAR-X, an extended version of the statistically consistent, coalescent-based method STELAR (Species Tree Estimation by maximizing tripLet AgReement) [ 22 ]. STELAR-X achieves unprecedented scalability through a combination of algorithmic redesign and efficient data representations. We introduce a new, compact integer tuple-based representation of tree bipartitions that avoids traditional O ( n 2 k ) bitset-based encoding used in widely used methods like ASTRAL. We also used a customized double-hashing scheme based on permutation-invariant and associative hash functions with provably negligible collision probability. In addition, we introduce optimized CPU and GPU parallelization to accelerate computation. These innovations yield an asymptotically optimal memory complexity of O ( nk ), ensuring that analyses remain feasible whenever the input gene trees fit in memory. Combined with additional algorithmic optimizations, STELAR-X reduces the running time of the original STELAR from O ( n 4 k 3 ) to O ( n 2 k 2 ). In comparison with ASTRAL-MP, the most scalable variant of ASTRAL, STELAR-X demonstrated dramatic performance improvements: on datasets with 10,000 species and 1,000 genes, it ran 712 × faster and used 7.5× less memory. ASTRAL-MP was shown to scale to a 10,000-species dataset [ 23 ] which required 15 hours of computation and 123GB memory in our experiment, whereas STELAR-X completed the same scale of analysis within only two minutes using only 20GB memory. Remarkably, STELAR-X can analyze datasets with 100,000 species and thousands of genes in under 8.5 hours using 86 GB of memory, and datasets with 100,000 genes and 1,000 taxa in just 4 minutes using 106 GB memory – a level of scalability that represents a significant advance and establishes a new benchmark for statistically consistent species tree inference. 2 Materials and Methods 2.1 Problem Definition Let 𝒢= { g 1 , g 2 , …, g k } be a collection of k binary rooted gene trees, each defined on the same set 𝒳 of n taxa. For any set of three taxa { a, b, c }, let ab | c denote the triplet tree where a and b form a cherry and c is the outgroup. The three possible triplet topologies for a set { a, b, c } of taxa are ( ab | c, bc | a, ca | b ). Let τ ( t ) represent the set of all triplets induced by a tree t . The problem of constructing species trees by maximizing triplet consistency with the input gene trees is defined as follows. The species tree reconstruction problem by maximizing triplet consistency seeks for a species tree T on χ that maximizes the triplet score 2.2 Background: overview of STELAR For a rooted, binary tree t , each internal node u induces a subtree bipartition ( A | B ) where A and B are the leaf sets of the two child subtrees of u [ 26 ]. Let 𝒮 ℬ𝒫 s( t ) denote the set of internal bipartitions of t . Then the collection of subtree-bipartitions in the set 𝒢 of gene trees is 𝒢 ℬ = ∪ i 𝒮 ℬ𝒫 ( g i ). We further define 𝒰𝒢 ℬ as the set of unique subtree-bipartitions from ;𝒢 ℬ. STELAR infers a species tree ST using a dynamic programming approach that recursively identifies the optimal (in terms of maximizing the triplet consistency) subtree-bipartitions at each level in a top-down manner [ 22 ]. Note that any triplet on { a, b, c } is mapped to a unique internal node u in T (the least common ancestor of { a, b, c } in T ), and this node in turn induces a subtree-bipartition ( A | B ). Consequently, the triplet consistency score of a candidate species tree ST can be equivalently expressed as a sum over the scores for the subtree-bipartitions in 𝒮 ℬ𝒫 ( ST ). Let w 𝒢 ( x ) denote the weight of a subtree-bipartition x (the number of triplets in 𝒢 that map to x ). STELAR reconstructs the species tree by dynamically selecting subtree-bipartitions from a candidate set 𝒞 ℬ according to the following recursive formulation: where V ( A ) is the optimal triplet score achievable on cluster C ⊆ 𝒳. If 𝒞ℬ contains all possible bipartitions, we obtain an exact but exponential time algorithm. In the constrained version of STELAR, 𝒞ℬ is restricted to only those bipartitions observed in the input gene trees, i.e., 𝒞ℬ = 𝒰𝒢ℬ . 𝒞ℬ can also be considered as a modest extension of by 𝒰𝒢ℬ adding extra bipartitions for handling extensively incomplete gene trees. STELAR, including its constrained version, is a statistically consistent approach for species tree estimations [ 22 ]. 2.3 Overview of STELAR-X To extend STELAR for the analysis of ultra-large phylogenetic datasets, we introduce algorithmic and data-structure innovations in STELAR-X: a compact tuple representation of subtree bipartitions, a permutation-invariant double-hashing scheme for frequency mapping, GPU-accelerated precomputation of bipartition weights, and an efficient dynamic-programming solver that uses the precomputed maps. As we demonstrate theoretically ( Section 2.6 ), the computation of weights constitutes the primary bottleneck in terms of running time. The structure of this computation, however, makes it particularly well-suited for Single Instruction Multiple Data (SIMD) execution [ 27 ]. We therefore isolate this step as a standalone routine and run it with GPU parallelization beforehand (discussed in Section 2.8 ). In the earlier version of STELAR, all subtree-bipartitions were represented as bitsets, the unique ones were extracted subsequently, and bitwise operations were used to calculate weights. With bitset representations, even a single taxon is represented by a bit vector of length n . For datasets with hundreds of thousands of taxa, this strategy leads to prohibitive RAM consumption and running time. To address this scalability challenge, STELAR-X represents each subtree bipartition by a fixed-length integer tuple derived from the postorder leaf array of its source gene tree ( Section 2.4 ). It maps equivalent subtree-bipartitions (which may appear in different gene trees and in swapped order) to a unique hash signature using a customized double hashing, which makes collisions vanishingly rare, and accumulates frequencies for a subtree-bipartition in a hash table ( Section 2.5 ). Using this frequency map, STELAR-X precomputes the weight w 𝒢 ( x ) for all x ∈ 𝒞 ℬ by summing contributions from all unique subtree-bipartitions. This embarrassingly parallel reduction is offloaded to the GPU ( Section 2.8 ). Finally, we build a cluster → subtree-bipartition map and run the DP ( Equation 1 ) using table lookups for precomputed weights ( Section 2.7 ). Figure 1a shows the overall algorithmic flow of STELAR-X. Download figure Open in new tab Figure 1: (a) Algorithmic framework of STELAR-X integrating double-hashing-based frequency mapping, GPU-accelerated weight precomputation, and dynamic programming for species tree inference. (b) Illustration of frequency mapping using double hashing. Three subtree bipartitions ( B | CDE ), ( EA | C ), and ( CA | E ) are considered from three gene trees. Since the bipartitions ( EA | C ) ∈ 𝒮ℬ 𝒫 ( T 2 ) and ( C | AE ) ∈ 𝒮ℬ 𝒫 ( T 3 ) are equivalent, they share the same hash signature, yielding a frequency of 2. 2.4 Compact tuple representation of subtree bipartitions For each gene tree g i we form an array 𝒜 i of its leaf labels in a postorder traversal. Any internal node in g i induces a bipartition ( A | B ) where A and B , by construction, correspond to two adjacent contiguous subarrays of 𝒜 i . Let 𝒜 i,l,r denote the subarray of 𝒜 i from indices l to r (i.e., 𝒜 i [ l : r ]). Then, if and , the bipartition ( A | B ) can be represented as the tuple ( i, l 1 , r 1 , l 2 , r 2 ), where l 1 < r 1 < l 2 < r 2 . In fact, since l 2 = r 1 + 1, four integers suffice to store the bipartition. This tuple representation reduces storage from O ( n ) bits per bipartition to a constant number of machine words, giving an overall space of O (|𝒰𝒢ℬ|) words. Because |𝒰𝒢ℬ| = O ( nk ), the storage for the unique bipartitions is O ( nk ) words, while the usual bitset representations would take O ( n 2 k ) space. We present an example of this representation in Supplementary Material ( Section 1 ). 2.5 Frequency mapping of subtree-bipartitions using permutation-invariant and associative double hashing We now describe the efficient construction of the frequency map f G ( x ) of a subtree-bipartition x ∈ 𝒰𝒢ℬ across all gene trees in 𝒢 under the compact integer-tuple representation. Equivalence of bipartitions Let P and Q be sets of taxa; we write P ∼ Q if they contain the same taxa, regardless of order. Two subtree-bipartitions x = ( A 1 | B 1 ) and y = ( A 2 | B 2 ) are equivalent ( x ≡ y ) if either A 1 ∼ A 2 and B 1 ∼ B 2 , or A 1 ∼ B 2 and B 1 ∼ A 2 . Thus, equivalence is invariant under both taxon ordering and side swapping. For the tuple representation of bipartitions x = ( i x , l 1 x , r 1 x , l 2 x , r 2 x ) and y = ( i y , l 1 y , r 1 y , l 2 y , r 2 y ), equivalence is possible only when i x ≠ i y (i.e., two bipartitions originate from different gene trees). Bipartitions within the same gene tree ( i x = i y ) are either disjoint or one contains the other. A naive cross-tree comparison to detect equivalence would require O ( n ) time per pair. To eliminate this overhead, we adopt a hashing-based approach that detects equivalence in O (1) time. Permutation-invariant double hashing Let ϕ be permutation-invariant and associative hash function that maps a set of taxa to a single hash value independent of order. If x ≡ y , by definition of equivalence, either and , or the similar relations with the two sides swapped. Since ϕ is permutation-invariant, these relations imply or the corresponding equalities under a side swap. Although equal hash values suggest possible equivalence, hash collisions prevent a strict guarantee. To make the probability of collisions negligible, we employ two safeguards. First, we apply double hashing: two independent permutation-invariant and associative hash functions, ϕ 1 and ϕ 2 , produce a composite signature ( ϕ 1 , ϕ 2 ) for any set of taxa. Second, we apply a per-element hash function ℋ to each taxon identifier, mapping it into via multiplication and bitwise operations modulo 2 k so that 2 k is large. This sparse projection mitigates structural collisions common to contiguous integer labels. For any taxon t ∈ 𝒳, let id(( t ) ∈ {0, …, n −1} denote its identifier. For a subset S ⊆ 𝒳, we define its set-level signature as σ ( S ) = ϕ 1 ({ℋ (id( t )) : t ∈ S }), ϕ 2 ({ℋ (id( t )) : t ∈ S }). Consequently, for a bipartition x = ( A | B ), the composite signature is ( σ ( A ), σ ( B )). Now, since the sets A and B represent subarrays of 𝒜 i , we need to efficiently compute ϕ 1 ({ℋ (id(𝒜 i,j ))} l ≤ j ≤ r ) and ϕ 2 ({ℋ (id(𝒜 i,j ))} l ≤ j ≤ r ) for any required subarray 𝒜 i,l,r . To this end, we precompute prefix-scan arrays for ϕ 1 and ϕ 2 . For an associative hash function ϕ admitting a cancellation operator ⊖ (e.g., subtraction for addition, XOR for XOR), we define for each array 𝒜 i the prefix array 𝒫 i where, for 1≤ m ≤ n . Then for any subarray 𝒜 i,l,r , the hash value of the corresponding taxon set is obtained in constant time as, with the convention that is the identity element of ϕ . We construct such prefix arrays independently for both ϕ 1 and ϕ 2 , enabling O (1) evaluation of any required subarray hash value. Further details on the hashing scheme, along with an example hash-signature computation, are provided in Supplementary Material ( Section 2 ). This combination of double hashing and sparse integer mapping makes collisions vanishingly rare (see the collision analysis in Theorem 2.1 ). In our implementation, ϕ 1 is addition and ϕ 2 is XOR over , and we observed no hash collisions over extensive evaluation. All arithmetic is performed modulo 2 k so that 2 k is large (we use k = 64). A modulus of the form 2 k is convenient for two reasons: it preserves the associativity and group structure of bitwise operations, and it is computationally efficient because it naturally arises from the wrap-around behavior of fixed-width integer types. Finally, the frequency f G ( x ) of each unique bipartition x ∈ 𝒰𝒢ℬ is derived by inserting the computed signatures into a hash table and counting the number of bipartitions that map to the same hash value. Figure 1b schematically illustrates this process. Theorem 2.1 (Collision Probability Bound). Let σ ( S ) = ( ϕ 1 ({ r t : t ∈ S )}, ϕ 2 ({ r t : t ∈ S })) be the double-hash signature of a set S of taxa, where ϕ 1 , ϕ 2 are independent permutation-invariant hash functions modulo M and each r t = ℋ (id( t )) is independently and uniformly distributed in Z M . Among B total bipartitions, the probability that at least one collision will occur is bounded by Proof . See Supplementary Material ( Section 3 , Theorem 3.1 ) Thus, to keep this probability below a prescribed tolerance δ , it suffices to ensure that . Hence, choosing M ( M = 2 k ) sufficiently larger than B ( B = Θ( nk )) renders global collisions negligible in practice. 2.6 Precomputation of Bipartition Weights We next justify and describe the precomputation of weights associated with all candidate bipartitions in 𝒞 ℬ. This step is essential for the dynamic programming (DP) phase of STELAR, whose state space is defined by the recursive formulation in Equation (1) . The DP begins with the full taxon set 𝒳 and recursively partitions each cluster using subtree-bipartitions. Consequently, every transition depends on the availability of subtree-bipartition weights. We now show in Theorem 2.2 that, in the constrained version of STELAR, this process inevitably requires the weights of all subtree-bipartitions in 𝒞 ℬ. Theorem 2.2. For the constrained version (i . e., 𝒞 ℬ = 𝒰𝒢ℬ ), the DP state space of STELAR spans every bipartition x ∈ 𝒞 ℬ. Proof . The proof is provided in the Supplementary Material ( Section 4 , Theorem 4.1 ). □ Precomputing these weights therefore does not introduce redundant computation. Moreover, even when 𝒰𝒢ℬ ⊊ ∈ 𝒞 ℬ, precomputing weights for all x ∈ 𝒞 ℬ remains practical, provided that |CB| is not asymptotically larger than |𝒰𝒢ℬ|. Weight formulation Let x = ( A 1 | B 1 ) ∈ 𝒞 ℬ be a candidate bipartition and y = ( A 2 | B 2 ) ∈ 𝒮ℬ𝒫 ( g i ) a bipartition from gene tree g i . Following [ 22 ], the number of triplets simultaneously mapped to both x and y is where 𝒩 𝒯 ( n 1 , n 2 ) is the number of triplets mapped to a bipartition ( A | B ) with | A | = n 1 , | B | = n 2 : The total weight of x across all gene trees is then . Using the precomputed frequency mapping f ℬ ( y ) of unique bipartitions y ∈ 𝒰𝒢ℬ produced by the double hash table, this can be written more efficiently as, Note that each M ( x, y ) requires computing the four intersection cardinalities between clusters | A 1 ∩ A 2 |, | B 1 ∩ B 2 |, | A 1 ∩ B 2 |, | A 2 ∩ B 1 | ( Equations (2) and (3) ). Efficient intersection counting using tuples To avoid memory-intensive bitset operations, we employ our proposed integer-tuple representation of subtree-bipartitions. Let and denote two clusters ( i ≠ j ). We have | X | = r x − l x + 1 and | Y | = r y − l y + 1. The intersection | X ∩ Y | is computed by iterating over each taxon in the smaller cluster and checking taxon membership in the other cluster. To optimize this membership testing, we precompute index maps π i ( v ), where π i ( v ) gives the position of taxon v in the post order array representation A i of g i . Thus, for each taxon , we check whether l y ≤ π j ( v ) ≤ r y (assuming | X | < | Y |) and accumulate the intersection count. This procedure runs in O (min(| X |, | Y |)) time per intersection. Supplementary Section 1 presents an example showing the computation of M ( x, y ). Assuming balanced gene trees, the total time for precomputing all w 𝒢 ( x ) over 𝒰 𝒢ℬ is O ( n 2 k 2 ) ( Theorem 2.3 ). Therefore, this is the dominant part of the overall running time of STELAR-X (see Section 2.9 ). This justifies isolating the weight precomputation as a separate stage, which we further accelerate using GPU parallelization (see Section 2.8 ). Theorem 2.3. For the constrained version (i . e., 𝒞 ℬ ) = 𝒰 𝒢ℬ ), if each gene tree is a perfectly balanced rooted binary tree with n = 2 d taxa, then the precomputation of weights requires O ( n 2 k 2 ) time . Proof . The proof is provided in the Supplementary Material ( Section 4 , Theorem 4.2 ). Although the analysis assumes balanced binary trees for mathematical simplicity, the practical runtime mainly depends on the smaller of the two subtrees in each bipartition pair. As a result, the observed running time typically remains close to the theoretical bound. In the extreme case of highly imbalanced fully caterpillar-like gene trees, the precomputation requires 𝒪( n 3 k 2 ) time ( Theorem 2.4 ). In practice, however, this effect is alleviated because the number of unique bipartitions |𝒰 𝒢ℬ| is generally much smaller than nk , making the balanced-tree assumption a good approximation of empirical behavior. Theorem 2.4. Assume 𝒞 ℬ = 𝒰 𝒢ℬ. If each gene tree is a rooted caterpillar on n taxa, then the precomputation of weights (evaluating ℳ ( x, y ) for all ordered pairs x, y ∈ 𝒰 𝒢ℬ ) requires 𝒪( n 3 k 2 ) time . Proof . The proof is provided in the Supplementary Material ( Section 4 , Theorem 4.3 ). □ 2.7 Execution of Dynamic Programming As the final stage, we execute the dynamic programming (DP) procedure defined by Equation (1) . Each DP state corresponds to a cluster of taxa, and transitions require identifying all subtree-bipartitions x ∈ 𝒞 ℬ that partition the taxa in the current cluster. To enable efficient lookup, we precompute a state-space mapping Ψ from clusters C ⊆ 𝒳 to the set of candidate bipartitions. For each subtree-bipartition x = ( A | B ) ∈ 𝒞 ℬ, we define its associated cluster C = A B and construct a mapping. Here, again, we employ the double-hashing scheme as before and avoid the memory-intensive bitset representation. Each cluster C is encoded using the pair of hash signatures ( ϕ 1 ( C ), ϕ 2 ( C )). During DP ( Eq. 1 ) we enumerate Ψ( C ) to obtain allowed subtree-bipartitions and fetch w 𝒢 ( A | B ) in O (1) time per bipartition using the precomputed weight map discussed earlier ( Section 2.6 ). Because both the state space (clusters) and candidate bipartitions are encoded via compact signatures, memory demand remains O (| 𝒞 ℬ | + |𝒰 𝒢ℬ |.) = O ( nk ). The DP itself then runs in time proportional to the number of state transitions (i.e., the total number of candidate bipartitions considered), plus any bookkeeping overhead. 2.8 Parallelization We next identify the stages of our algorithm that are amenable to CPU and GPU parallelization and describe their implementations on multicore CPUs and GPUs. We assume T C CPU threads and T G GPU threads, representing the degrees of parallelism under ideal load balancing and negligible communication overhead. CPU Parallelization CPU parallelism is applied primarily to the processing of the k input gene trees. The collection of gene trees is divided into T C approximately equal partitions, each assigned to an independent thread running in parallel. Within each thread, the parsing, subtree–bipartition extraction, and frequency mapping steps are executed sequentially on the assigned subset. When necessary, thread-safe containers and synchronization primitives are employed to ensure correct aggregation of shared data across threads. GPU Parallelization The most computationally intensive stage, computing the weight w G ( x ) for each candidate bipartition x ∈ 𝒞 ℬ, requires evaluating M( x, y ) for all y ∈ 𝒰 𝒢 ℬ. This corresponds to executing the same operation for O (| 𝒞 ℬ||𝒰 𝒢 ℬ|) bipartition pairs, followed by accumulation along the UGB dimension to obtain the weights of O (| 𝒞 ℬ|) candidate bipartitions. Therefore, we offload this highly regular computation pattern to T G GPU threads. We transfer the post-order leaf traversal arrays, the frequency map, and the index map to GPU. For each candidate bipartition x ∈ 𝒞 ℬ, each GPU thread computes the intersection counts for a distinct ( x, y ) pair, and results are accumulated by a reduction across to 𝒰𝒢ℬ obtain the aggregated weights. Additional optimizations, such as shared-memory tiling and coalesced access patterns, are used to reduce memory latency and improve throughput. The resulting weight map of size O (| 𝒞 ℬ|) feeds the dynamic programming algorithm. 2.9 Complexity Analysis Theorem 2.5 (Running time and memory complexity). For n taxa, k gene trees, T C CPU threads and T G GPU threads, STELAR-X runs in time (under the balance gene tree assumption), O ( nk + |𝒰 𝒢 ℬ| + | 𝒞 ℬ|) CPU memory, and O (|𝒰 𝒢 ℬ| + | 𝒞 ℬ|) GPU memory. In the worst case, when all gene trees are caterpillars, the running time becomes . Proof .The proof is provided in Supplementary Material ( Section 5 , Theorem 5.1 ). □ In practice, the precomputation complexity depends on |𝒰 𝒢 ℬ| and | 𝒞 ℬ|. Under lower levels of ILS, tends to be substantially smaller than nk , leading to a reduced effective running time. Consequently, the degree of ILS directly influences the practical computational cost of the algorithm. In case of memory usage, since both |𝒰 𝒢 ℬ| and | 𝒞 ℬ| can be bounded by O ( nk ) in the constrained case, the overall CPU and GPU memory usage scales as O ( nk ). If only the unique bipartitions were represented using traditional bitset-based representations for weight computation, the memory usage would depend on the number of distinct bipartitions, and thus on the degree of ILS. In contrast, STELAR-X employs a compact tuple-based representation throughout, achieving asymptotically optimal memory usage of O ( nk ) that matches the input size, regardless of the ILS level. This claim about the impact of ILS on scalability is further confirmed in our empirical results (see Section 3.2 and Supplementary Figure S2 ). 3 Results 3.1 Experimental Setup We evaluated STELAR-X on both simulated and empirical datasets. To assess scalability, we compared its performance with ASTRAL-MP [ 23 ], the only existing multi-parallel summary method, and ASTER [ 28 ], which implements ASTRAL-IV, a faster variant of ASTRAL. For accuracy assessment, we further compared STELAR-X with ASTRAL-MP [ 23 ], WQFM-TREE [ 29 ], ASTER [ 28 ], and Triplet MaxCut (TMC) [ 30 ]. All experiments were conducted on a Linux server equipped with an NVIDIA RTX 4090 GPU (24 GB VRAM) and an AMD EPYC 7742 processor with 32 active cores and 129 GB of RAM. Each analysis was allocated a maximum runtime of 48 hours. Simulated Datasets For the scalability analysis, we simulated large phylogenomic datasets under the Multispecies Coalescent (MSC) model using SimPhy [ 31 ]. In one set of experiments, we fixed the number of gene trees ( k ) at 1,000 and varied the number of taxa ( n ) from 1,000 to 100,000. In another set, we fixed n at 1,000 and varied k from 1,000 to 100,000. All datasets were generated under four model conditions corresponding to different levels of incomplete lineage sorting (ILS), ranging from low (ILS-L1) to medium-high (ILS-L4). The average gene tree discordance corresponding to these ILS levels is reported in Supplementary Table S2 . To further assess the robustness of scalability, we used three more existing simulated datasets with 500-10,000 taxa (see Section 3.2 ). Additionally, to evaluate accuracy, we used smaller simulated datasets containing 37, 100, 200, and 500 taxa since existing methods do not scale to very large datasets. Simulation parameters are provided in Supplementary Material (Section 6). Biological Datasets We analyzed two biological datasets: the avian dataset comprising 48 taxa and 14,446 genes [ 32 ], and an extended avian dataset comprising 363 taxa and 63,430 genes [ 33 ]. The gene trees were rooted using outgroups (see details in Supplementary Section 7). 3.2 Results on Scalability Analysis To assess the scalability of STELAR-X, we experimented on simulated datasets with large numbers of taxa and gene trees under medium ILS level (ILS-L2). We report the running time, CPU memory usage, and GPU VRAM consumption averaged over 5 replicates. In the first set of experiments, we fixed the number of gene trees at k = 1,000 and varied the number of taxa n from 1,000 to 100,000. Within our resource limits (128 GB CPU memory and a 48-hour of analyses), ASTRAL-MP and ASTER could be executed only up to 10,000 and 7,500 taxa respectively, consistent with the scalability reported in the original studies. Consequently, we compared the methods on datasets up to these size limits ( Figure 2a ). Across all tested cases, STELAR-X consistently and substantially outperformed ASTRAL-MP and ASTER in both running time and CPU memory usage, while exhibiting a comparable trend with ASTRAL-MP in GPU VRAM utilization. In particular, ASTER cannot benefit from GPU parallelism and thus consistently took substantially longer time than STELAR-X and ASTRAL-MP, yet its CPU RAM utilization was lower than ASTRAL-MP in all cases. Specifically, STELAR-X analyzed the dataset with 10,000 taxa in only 77 seconds, achieving a 712× speedup over ASTRAL-MP and a 7.5× reduction in CPU memory. Notably, ASTRAL-MP reached the resource limit (128 GB of CPU memory) at 7,500 and 10,000 taxa, whereas STELAR-X required only 11.9 GB and 16.4 GB for these two cases. As evident in Figure 2 , both the running time and memory growth rates of STELAR-X are markedly lower than those of ASTRAL-MP, reflecting the asymptotically optimal O ( nk ) space usage achieved by our new tuple-based representation and algorithmic re-engineering. Given the observed trend, ASTRAL-MP and ASTER would require prohibitive time and memory to analyze datasets beyond 10,000 taxa, while STELAR-X remains computationally feasible well beyond this range. Download figure Open in new tab Figure 2: Average running time, CPU RAM, and GPU VRAM requirements of STELAR-X, ASTRAL-MP, and ASTER over 5 replicates (except for 10,000-taxon and 50,000-gene conditions where ASTRAL-MP was run on one replicate and ASTER could not be run due to their high computational demands). (a) 1,000 gene trees with 1,000–10,000 taxa, (b) 1,000 taxa and 1,000–50,000 genes. Next, we evaluated the scalability with respect to the number of genes while fixing the number of species at n = 1,000. ASTRAL-MP reached the 128 GB memory limit at 50,000 genes while ASTER exceeded the time limit beyond only 25,000 genes. As shown in Figure 2b , STELAR-X was consistently faster and more memory-efficient across all tested dataset sizes. For example, on the 50,000-gene dataset, ASTRAL-MP required 75 minutes and 123.5 GB of CPU RAM, whereas STELAR-X completed the analysis in 140 seconds using 60.7 GB of CPU RAM—an approximate 32.2× speedup with a 2× reduction in memory usage. GPU VRAM usage remained moderate (0.4 ∼ 0.8 GB) for both methods, with STELAR-X showing slightly higher requirements. To assess the robustness of scalability, we next compared the performance of STELAR-X and ASTRAL-MP on three existing simulated datasets comprising 500-10,000 taxa and 1,000 genes using both true and estimated gene trees. STELAR-X remained substantially faster and more memory-efficient across all cases (see Supplementary section 9.2). Scaling up the number of taxa and gene trees To further evaluate our performance at a larger scale (beyond the limits of existing methods), we evaluated STELAR-X on datasets with up to 100,000 taxa and 100,000 genes. In the first experiment, we fixed k = 1,000 and increased n from 1,000 to 100,000 ( Figure 3a ). Consistent with our theoretical expectations, CPU memory usage exhibited an approximately linear growth, while GPU VRAM usage followed an almost perfectly linear trend. STELARX successfully analyzed the 100,000-taxon dataset in about 8.5 hours using 86 GB of CPU RAM and 1.3 GB of GPU VRAM. For comparison, ASTRAL-MP required 120 GB of CPU memory to process only 7,500 taxa, and extrapolations from its growth curve suggest that analyzing 100,000 taxa would be practically infeasible for ASTRAL-MP. In contrast, given the observed linear scaling of memory and substantially faster runtime, STELAR-X is expected to handle substantially larger datasets ( > 100,000 taxa) on machines with a few hundred gigabytes of RAM (e.g., 256 GB) and modest multi-day runtimes. Download figure Open in new tab Figure 3: Average running time, CPU RAM, and GPU VRAM usage of STELAR-X on large datasets over 5 replicates (except for the 100,000-taxon case where we analyzed one replicate). (a) 10,000 to 100,000 taxa with 1,000 gene trees, (b) 1,000 taxa with 10,000 to 100,000 gene trees. In the second experiment, we fixed n at 1,000 and varied k from 1,000 to 100,000 ( Figure 3b ). Notably, STELAR-X scaled even more efficiently with increasing numbers of genes, exhibiting nearly linear growth in runtime. Remarkably, it analyzed 100,000 genes in just 240 seconds using 106 GB CPU RAM– an unprecedented scale not achievable by ASTRAL-MP or other existing summary methods. CPU RAM and GPU VRAM usage remained low and continued to follow the same linear pattern. Impact of varying ILS Next, we analyzed the effect of varying levels of ILS on the running time and memory consumption of STELAR-X using simulated datasets comprising 10,000–40,000 taxa with 1,000 genes and 1,000 taxa with 1,000–100,000 genes under four model conditions, ranging from low (ILS-L1) to medium-high (ILS-L4) levels of ILS (see Supplementary Figure S2 ). Consistent with our complexity analysis ( Section 2.9 ), the running time increases with higher levels of ILS, whereas CPU RAM and GPU VRAM usage remain nearly constant, showing only minor variations due to small constant factors, thus maintaining the same linear scaling trend. For example, with 40,000 taxa, the running time increased by 3.7× from ILS-L2 to ILS-L4, while CPU RAM and GPU VRAM consumption rose only slightly, from 49 GB to 53 GB and from 0.78 GB to 0.85 GB, respectively. As the number of gene trees increased, this trend became more pronounced, with memory usage showing only negligible variation across ILS levels. 3.3 Results on Accuracy of Inference We conducted experiments on simulated datasets with 100, 200, and 500 taxa and compared the average accuracy of STELAR-X with ASTRAL-MP [ 23 ], WQFM-TREE [ 29 ], ASTER [ 28 ], and TMC [ 30 ]. We could not run TMC on the 500-taxon dataset due to its high computational demand (see Supplementary Section 9.1). Since TMC’s accuracy was markedly lower than that of others, we report its results in the Supplementary Material ( Section 9.3 ). We also analyzed a biologically-based 37-taxon simulated mammalian dataset previously studied in [ 34 ]. On the 37-taxon datasets ( Figures 4a,b ), STELAR-X showed accuracy comparable to ASTRAL-MP, wQFM-TREE, and ASTER across varying levels of ILS and gene tree estimation error (varied by sequence length), with no statistically significant differences among methods ( p > 0.05). STELAR-X was slightly more accurate than ASTRAL-MP on model conditions with high (0.5X) and moderate (1X) levels of ILS. wQFM-TREE achieved the highest accuracy in almost all cases. Similar patterns were observed for the 100–500-taxon datasets ( Figure 4c ), although STELAR-X displayed slightly higher RF rates on 100 and 200 taxa. Download figure Open in new tab Figure 4: (a)-(c) Average RF rates of STELAR-X, ASTRAL-MP, WQFM-TREE, and ASTER over 10 replicates (a) varying ILS (b) varying sequence lengths (37 taxa) (c) 100–500 taxa (d) RF rates on 1,000–10,000 taxa over 5 replicates except for ASTRAL-MP (1 replicate) and ASTER on 10,000 taxa To further assess accuracy at larger scales, we compared STELAR-X, ASTRAL-MP, ASTER on datasets spanning 1,000–10,000 taxa (excluding ASTER on 10,000 taxa due to time limit) ( Figure 4d ). wQFM-TREE could not be run on these datasets within our resource limits and was therefore excluded. For the 1,000-, 2,500-, and 10,000-taxon datasets, STELAR-X matched or exceeded ASTRAL-MP in accuracy, while modestly higher RF error rates were observed in the other two cases. Nonetheless, overall RF errors remained low, as the true gene trees (instead of estimated gene trees) under moderate levels of ILS were used, as sequence simulation and gene tree estimation for these large dataset sizes were computationally prohibitive. 3.4 Results on Biological Datasets We evaluated the avian dataset comprising 48 taxa and 14,446 genes [ 32 ]. STELAR-X analyzed the avian dataset in only 12 seconds, achieving a 30× speedup over ASTRAL-MP. As shown in Figure 5 , both STELAR-X and ASTRAL-MP accurately reconstructed the major clades Australaves, Afroaves, Cuprimulgimorphae, Core Waterbirds and Columbimorphae. None of the methods could reconstruct the Cursores and Otidimorphae clades. Download figure Open in new tab Figure 5: (a)-(c) Estimated trees on the avian dataset with identical clades indicated. Branch supports (BS) based on quartet-based local posterior probabilities [ 35 ] are shown on branches. All BS values are 100% except where noted. We also analyzed an extended avian dataset comprising 363 taxa and 63,430 genes [ 33 ]. STELAR-X completed this analysis within 1.5 hours. It correctly reconstructed all 218 families, 37 orders, and 11 out of the 12 major clades (see Supplementary Section 8.2.2 for details). 4 Conclusions We presented a statistically consistent coalescent-based summary method STELAR-X, a substantially redesigned and computationally efficient extension of the triplet-based summary method STELAR. At the core of STELAR-X is a compact integer-tuple representation of subtree-bipartitions that replaces the bitset encodings used in established methods such as ASTRAL. This redesign enables extensive algorithmic optimizations and re-engineering, including efficient pre-computation of bipartition weights using a customized double-hashing technique and a streamlined dynamic programming strategy with greatly reduced computational overhead. By further utilizing GPU acceleration for highly regular weight pre-computations, STELAR-X delivers substantial improvements in both running time and memory efficiency. Our experiments demonstrate that STELAR-X maintains competitive accuracy with ASTRAL-MP and wQFM-TREE. Most notably, STELAR-X delivers unprecedented scalability, and can infer species trees from datasets comprising 100,000 taxa and 100,000 genes in few hours of computation using only 100 GB of memory, whereas current approaches encounter prohibitive memory and runtime limitations well below this scale. Moreover, STELAR-X can be used within divide-and-conquer frameworks [ 24 , 25 ] to analyze millions of taxa. This opens the door to statistically consistent phylogenomic analyses for ambitious community initiatives to resolve the tree of life across diverse lineages, such as constructing a comprehensive tree of life for all ∼ 330,000 known species of flowering plants (angiosperms) [ 36 , 37 ]. Beyond scalability, the new data structures and algorithmic redesign introduced here can benefit other coalescent-based tools, including ASTRAL. STELAR-X is a triplet-based method and thus requires rooted gene trees. As a next step, we will extend STELAR-X to unrooted and multi-copy gene family trees to account for both orthology and paralogy, and evaluate it on large empirical datasets spanning complex evolutionary histories. Supplementary material 1 Example: Tuple Representation of Bipartitions and Computation of ℳ ( x, y )) We assume 1-based array indexing for this example. Consider two trees T 1 and T 2 defined over the same taxa set { A, B, C, D, E }: We consider the following two subtree-bipartitions ( x in T 1 and y in T 2 ): We first illustrate how bipartitions are represented under the post-order leaf traversal. For T 1 , the traversal array is 𝒜 1 = { A, B, C, D, E }. Let an internal node X induce the subtree bipartition x = ( B | CDE ). This bipartition x is represented as the integer tuple (1, 2, 2, 3, 5), where i = 1, l x = 2, r x = 2, l y = 3, and r y = 5. Similarly, for T 2 , the traversal array is 𝒜 2 = { E, A, C, D, B }. Let an internal node Y induce the subtree bipartition y = ( EA | C ). This bipartition is represented as the integer tuple (2, 1, 2, 3, 3), where i = 2, l x = 1, r x = 2, l y = 3, and r y = 3. We now compute ℳ ( x, y ), which involves determining the sizes of intersections between the corresponding sides of these two bipartitions ( Equation 2 in the main text). To facilitate efficient comparison between bipartitions originating from different trees, we first compute the index maps π 1 and π 2 . These mappings record, for each taxon, its position in the respective post-order traversal arrays 𝒜 1 and 𝒜 2 : For the intersection A 2 ∩ B 1 , we iterate over the smaller cluster A 2 = { E, A } and test membership in B 1 = { C, D, E } using the index maps π 1 and π 2 : Summing these indicators yields The remaining intersections are computed similarly by iterating over the smaller of the two clusters and summing membership indicators: These intersection counts are then used to compute M( x, y ). 2 Computation of Double Hash Signatures 2.1 Specification of Single-element Hash Function Implementation We implement the single-element hash function ℋ using a standard 64-bit multiplicative mixing scheme. For an integer taxon identifier m , the function applies a sequence of XOR–shift and multiplication steps: Here C 1 = 0x85ebca6b and C 2 = 0xc2b2ae35 are fixed 32-bit multiplicative constants commonly used in high-quality non-cryptographic hash functions (e.g., MurmurHash3). To avoid degenerate cases in prefix-based computations, we map the output value 0 to 1. The resulting function provides good dispersion of contiguous integer identifiers and minimizes structural collisions. 2.2 Example: Calculation of Double Hash Signature of Bipartitions with Prefix Scan Arrays We assume 1-based array indexing in this example. Consider the gene tree g i = (( D, B ), ( C , ( A, E ))) containing the set 𝒳= { A, B, C, D, E } of taxa. We consider a subtree-bipartition x = ( DB | CAE ) in g i , and illustrate how its double-hash signature is computed using prefix-scan arrays. We use two hash functions ϕ 1 and ϕ 2 , instantiated as addition and XOR, respectively. The taxa A – E are assigned integer identifiers 0–4 sequentially. For simplicity, let the single-element hash function be defined as (see the specification of the actual single-element hash function in Section 2.1 ). We consider a small modulus 2 7 = 128 for convenience of illustration. The post traversal array of g i is The bipartition x = ( DB | CAE ) is therefore encoded as the integer tuple ( i , 1, 2, 3, 5). Prefix-sum and prefix-XOR arrays over ℋ (id(𝒜 i,j )) are constructed as shown in Table S1 . We now compute the hash values for the two sides of the bipartition x = ( DB | CAE ) by applying the corresponding cancellation operators— subtraction for ϕ 1 and XOR for ϕ 2 —using the prefix-scan arrays. Side { D, B } of x . This corresponds to the range 𝒜 i [1 : 2]. Using the prefix arrays, One can verify that the sum of ℋ (id(𝒜 i,j )) over the range [1 : 2] is (54+108) mod 128 = 34. Likewise, the XOR over the same range is (54 ⊕ 108) mod 128 = 90. Thus, the signature of { D, B } is (34, 90). View this table: View inline View popup Download powerpoint Table S1: Example calculation of prefix scan arrays for two hash functions: addition and XOR on the traversal array 𝒜 i = { D, B, C, A, E } . Integer identifiers 0–4 are sequentially assigned to the taxa A – E . The single element hash function ℋ is assumed to be ℋ ( m ) = (101 m + 7) mod 128. All calculations are shown modulo 2 7 = 128. Side { C, A, E } of x . This corresponds to the range 𝒜 i [3 : 5]. From the prefix arrays, One can verify that the sum of ℋ (id(𝒜 i,j )) over the range [3 : 5] is (81 + 7 + 27) mod 128 = 115. Likewise, the XOR over the same range is (81 ⊕ 7 ⊕ 27) mod 128 = 77. Thus, the signature of { C, A, E } is (115, 77). Final signature Combining both sides, the double-hash signature of the bipartition x = ( DB | CAE ) is 3 Theoretical Analysis of Collision Probability Theorem 3.1 (Collision Probability Bound). Let σ ( S ) = ( ϕ 1 ({ r t : t ∈ S }), ϕ 2 ({ r t : t ∈ S })) be the double-hash signature of a set S of taxa, where ϕ 1 , ϕ 2 are independent permutation-invariant hash functions modulo M and each r t = ℋ (id( t )) is independently and uniformly distributed in Z M . Among B total bipartitions, the probability that at least one collision will occur is bounded by Proof . The key intuition is that collisions are rare because whenever two sets differ, at least one taxon contributes an independent random value, making accidental equality highly unlikely. Let 𝒳 be the taxon set with |𝒳 | = n . Let B be the number of subtree-bipartitions produced across all gene trees (in our setting, B = Θ( nk )). We choose a large modulus M and work in the ring ℤ M = { 0, 1, 2, … …, M − 1}. Setup A single-element hash maps each taxon identifier id( t ) to We idealize that the values { r t } t ∈ S are independent and uniformly distributed in ℤ M . We then apply two associative, permutation-invariant set-level functions ϕ 1 , ϕ 2 , each operating directly on subsets of { r t }. The signature of a set S is Single-set collision probability Let S ≠ T and define U = S \ T, V = T \ S . Associativity ensures that ϕ a admits a corresponding cancellation operator ⊖ (e.g. subtraction for addition, XOR for XOR, etc.), so that Because U ∪ V ≠∅, at least one r t appears only in one side. Conditioning on all other r t , the difference reduces to a function of the uniform random variable r t . This equals zero with probability at most 1 /M . Thus Pairwise signature collision Suppose the two set-level functions ϕ 1 and ϕ 2 are constructed so that their collision events are statistically independent (e.g. by using independent salts or structurally distinct definitions of ϕ a ). Then for distinct sets S, T , Collision probability for bipartitions Let bipartitions x = ( A 1 | B 1 ) and y = ( A 2 | B 2 ) be distinct (non-equivalent). A collision occurs if and only if Since each matching holds with probability 1 /M 2 , we obtain Global (any-pair) collision probability Among B bipartitions there are at most pairs. By a union bound, □ 3 Theoretical analysis of the precomputation of subtree-bipartition weights Theorem 4.1. For the constrained version (i . e., 𝒞ℬ = 𝒰 𝒢 ℬ), the DP state space of STELAR spans every bipartition x ∈ 𝒞ℬ . Proof . We argue by contradiction. Suppose there exists a bipartition x = ( A | B ) ∈ 𝒞ℬ that is not explored in the state space of the DP. We consider two possible cases: Case 1: A ∪ B = 𝒳 Since 𝒞ℬ = 𝒰 𝒢 ℬ , we have x ∈ 𝒢 ℬ . As A ∪ B covers all taxa, x corresponds to a root-level bipartition in one of the gene trees. By construction, such bipartitions are included in the search space at the very first state transition. This contradicts our assumption that x is not explored. Case 2: A ∪ B ≠ 𝒳 Again, x ∈ 𝒢 ℬ and hence arises from some internal node u of a gene tree g i , where the taxa covered by u form the set 𝒴 = A ∪ B . Since 𝒴 ⊊ 𝒳, u must have a parent node p in g i . Let the bipartition induced by p be y = ( C | D ). By construction, either C = 𝒴 or D = 𝒴. Thus, if y is explored in the DP state space, then the algorithm must also explore its child bipartition x , by design of the transition rules. Hence, the assumption that x is not explored implies that y is also not explored. Repeating this reasoning along the ancestor chain of u , we eventually reach the root of g i , where Case 1 applies and yields a contradiction. Since both cases lead to contradictions, our assumption is false. Therefore, every subtree-bipartition x ∈ 𝒰 𝒢 ℬ is necessarily explored in the constrained DP state space. □ Theorem 4.2. For the constrained version of STELAR (i . e., 𝒞ℬ = 𝒰 𝒢 ℬ), if each gene tree is a perfectly balanced rooted binary tree with n = 2 d taxa, then the precomputation of weights requires O( n 2 k 2 ) time . Download figure Open in new tab Figure S1: Running time analysis for computing intersection counts between two 8-taxon trees: (a) balanced binary trees and (b) caterpillar trees. Subtree bipartitions from each tree are shown, with numbers on partitions indicating the corresponding sizes. Proof . We analyze the worst-case scenario in which every bipartition across all gene trees is distinct, i.e., 𝒰 𝒢 ℬ = 𝒢 ℬ . The complexity for all other cases then follows immediately as a direct relaxation of this setting. By Equation 4 in the main manuscript ( w 𝒢 ( x ) = Σ y ∈𝒰 𝒢 ℬ f 𝒢 ( y ) ℳ ( x, y )), computing the weight of each candidate bipartition requires evaluating ℳ ( x, y ) against every y ∈ 𝒰 𝒢 ℬ . Thus we must evaluate ℳ ( x, y ) for every ordered pair ( x, y ) ∈ 𝒰 𝒢 ℬ × 𝒰 𝒢 ℬ . We bound the total cost by first bounding the cost between two fixed balanced trees and then summing over the tree-pairs. In a perfectly balanced rooted binary tree on n = 2 d leaves, an internal node at depth 𝓁 (root at depth 0) has subtree size n/ 2 𝓁 , and each of its two child subtrees has size s = n/ 2 𝓁 +1 . Thus the set of possible child-subtree sizes is and for a given child-subtree size s ∈ 𝒮 the number of internal nodes whose child-subtrees have size s equals the number of disjoint blocks of size 2 s that partition the n leaves, i.e. . Therefore the number of subtree-bipartitions in one balanced tree whose parts (child-subtrees) have size s is n/ (2 s ). Per-pair cost in terms of sizes We consider two bipartitions x = ( A 1 | B 1 ) in tree g p and y = ( A 2 | B 2 ) in tree g q , and let the child-subtree sizes be s and t , respectively. So | A 1 | = | B 1 | = s and | A 2 | = | B 2 | = t ). By Equation 2 in the main manuscript, ℳ ( x, y ) depends on four intersection counts among the parts of x and y . Each such intersection can be computed by iterating over the smaller argument using the index map π , hence the time to compute each intersection is O (min( s, t )). Since there are only a constant number of such intersections, the total cost to evaluate ℳ ( x, y ) is Cost between two balanced trees We now group bipartitions of g p and g q by their child-subtree sizes s = 2 i and t = 2 j (with 0 ≤ i, j ≤ d − 1). The number of bipartitions in g p with part-size s is n/ (2 s ), and similarly for g q with part-size t . Thus the number of ordered bipartition pairs with sizes ( s, t ) is , and the contribution of this size-class pair to the cost is Replacing s = 2 i and t = 2 j , the total cost between the two trees is An illustration of this analysis is shown in Figure S1a for a pair of balanced binary trees of 8 taxa. We now evaluate the double sum by symmetry. Splitting the domain into the two triangles i ≤ j and i > j : Both finite sums are uniformly bounded as d grows, since Σ Σ k ≥0 k/ 2 k = 2 and Σ k ≥0 1 / 2 k = 2. Hence and in fact the exact value is Therefore, the double sum is O (1). Hence S pq = O ( n 2 ). Thus, computing all pairwise intersection costs between bipartitions of two balanced trees costs O ( n 2 ). Extension to k trees There are k gene trees and thus k 2 ordered pairs of trees. Summing the O ( n 2 ) cost over all ordered pairs yields the total precomputation cost O ( n 2 ) · k 2 = O ( n 2 k 2 ), which completes the proof. □ Theorem 4.3. Assume 𝒞 ℬ = 𝒰 𝒢 ℬ. If each gene tree is a rooted caterpillar on n taxa, then the precomputation of weights (evaluating ℳ ( x, y ) for all ordered pairs x, y ∈ 𝒰 𝒢 ℬ) requires 𝒪 ( n 3 k 2 ) time . Proof . By Equation 4 in the main manuscript, the precomputation requires computing ℳ ( x, y ) for every ordered pair ( x, y ) ∈ 𝒰 𝒢 ℬ × 𝒰 𝒢 ℬ . We first bound the cost between two fixed caterpillar trees and then sum over all ordered tree pairs. Bipartitions in a rooted caterpillar . Fix a rooted caterpillar on n leaves arranged along the backbone. Its internal nodes (listed from the root downwards) induce the bipartitions of sizes Equivalently, for each L ∈ {1, …, n − 1} there is exactly one bipartition whose large side has size L (and the small side is size 1). Thus each caterpillar has exactly n − 1 subtree-bipartitions and the multiset of large-side sizes is {1, 2, …, n − 1} (each appearing once). Per-pair computation of ℳ ( x, y ) For two bipartitions x = ( A 1 | B 1 ) and y = ( A 2 | B 2 ) the equation 2 in main manuscript requires four intersection counts: | A 1 ∩ A 2 |, | A 1 ∩ B 2 |, | B 1 ∩ A 2 |, | B 1 ∩ B 2 |. In a rooted caterpillar at least three of these intersections involve a singleton side (size 1) and are therefore computable in O (1) time. The remaining intersection is the one between the two large sides (say sizes s and t ); this intersection can be computed in O (min( s, t )) time by iterating over the smaller large-side and checking membership via the index map. Thus the dominant cost for evaluating ℳ ( x, y ) is where s and t are the sizes of the large sides of x and y , respectively. Cost between two caterpillar trees Each of the two caterpillar trees has exactly one bipartition whose large-side size equals L for each L ∈ {1, …, n − 1}. Hence the total cost between two trees equals An illustration of this analysis is shown in Figure S1b for a pair of caterpillar trees of 8 taxa. Now, the inner double sum is a standard combinatorial sum; counting by the minimum value m = min( s, t ) gives For a fixed m , the number of ordered pairs ( s, t ) with min( s, t ) = m equals 2( n − 1 − m )+1 = 2 n − 2 m − 1. Therefore (Using the closed forms and one obtains the cubic bound.) Hence S pq = O ( n 3 ). Extension to k trees There are k gene trees and thus k 2 ordered tree-pairs. Summing the per-pair bound O ( n 3 ) over all ordered pairs yields the total precomputation cost which completes the proof. 5 Complexity analysis We now provide a theoretical analysis of the running time and memory requirement of STELAR-X. Theorem 5.1. For n taxa, k gene trees, T C CPU threads and T G GPU threads, STELAR-X runs in time (under the balance gene tree assumption), O ( nk + |𝒰𝒢ℬ| + |𝒞 ℬ|) CPU memory, and O (|𝒰𝒢ℬ| +(|𝒞 ℬ|) GPU memory .) In the worst case, when all gene trees are caterpillars, the running time becomes . Proof . We first derive bounds for the running time of STELAR-X. The parsing of the k input trees over T C CPU threads requires time. The subsequent computation of the frequency mapping, using the double-hashing approach, also requires time. This efficiency follows from the use of prefixscan arrays, which enable constant-time range hash evaluations. Next, the precomputation of weights, distributed across T 𝒢 GPU threads, requires time under the balanced gene tree assumption as derived in Theorem 4.2 . Finally, we analyze the running time of the dynamic programming (DP) algorithm. By Equation 1 in main manuscript and Theorem 4.1 , the size of the DP state space is at most O (|𝒞 ℬ|). Since both the state-space map and the weight map are precomputed, the DP algorithm itself executes in O (|𝒞 ℬ|) time. Putting all components together, the total running time of our algorithm under the assumptions that the trees are balanced and all the bipartitions are unique is, In the worst case, when all the trees are caterpillars, as derived in Theorem 4.3 , the precompution complexity becomes , and hence the total running time becomes, . We now analyze the memory requirements of our algorithm in both CPU RAM and GPU VRAM. On the CPU side, storing the k input gene trees over n taxa requires O ( nk ) memory. The efficient representation of subtree-bipartitions, together with their subsequent processing, also requires O ( nk ) memory. Storing the unique subtree bipartitions in 𝒰𝒢ℬ and 𝒞 ℬ requires O (|𝒰𝒢ℬ| + |𝒞 ℬ|) space. The dynamic programming algorithm requires O (|𝒞 ℬ|) additional space. Overall, the total CPU memory usage is therefore On the GPU side, memory usage is dominated by the precomputation of weights. Each bipartition is represented as a constant-length integer tuple. Consequently, the total GPU VRAM required for storing all O (|𝒰𝒢ℬ| + |𝒞 ℬ|) bipartitions is Since both |𝒰𝒢ℬ| and |𝒞 ℬ|can be bounded by O ( nk ) in the constrained case, the overall CPU and GPU memory consumption scales as O ( nk ), matching the asymptotic input-space complexity. □ 6 Dataset The average gene tree-gene tree (GT-GT) discordance and gene tree-species tree (GT-ST) discordance (in terms of RF rates) corresponding to four different levels of ILS are shown in Table S2 . Our simulation parameters corresponding to ILS-L2 are presented in Table S3 . For generating these four different ILS levels, we vary the maximum value of the uniform distribution of Effective Population Size from 150000 to 300000. View this table: View inline View popup Download powerpoint Table S2: Discordance levels under different ILS conditions analyzed in this study. We show the average gene tree-gene tree (GT-GT) and gene tree-species tree (ST) discordance, measured by average RF rates, under various levels of ILS. View this table: View inline View popup Download powerpoint Table S3: Simulation parameters used to generate gene trees and species trees using Simphy. 7 Rooting of Input Gene Trees For the avian dataset with 48 taxa and 14,446 genes, we rooted each gene tree using the outgroup taxa Struthio camelus (ostrich) and Tinamus guttatus (white-throated tinamou). For the extended avian dataset with 363 taxa and 63,430 genes, we rooted the gene trees using Acanthisitta chloris , which serves as an outgroup taxon (belonging to the outgroup clade Passeriformes) in that dataset. 8 Additional Results 8.1 Additional Results on the Impact of ILS Download figure Open in new tab Figure S2: Effect of varying levels of ILS on the running time and memory usage of STELAR-X across 4 model conditions, using simulated datasets with (a) 10,000–40,000 taxa and 1,000 gene trees (b) 1,000 taxa and 1,000-100,000 gene trees. 8.2 Additional Results on Biological Datasets 8.2.1 Comparison of Running Time and Memory Usage across Methods Table S4 compares STELAR-X, ASTRAL-MP, and ASTER on the avian dataset (48 taxa, 14446 gene trees) and the extended avian dataset (363 taxa, 63430 gene trees) in terms of running time, CPU memory consumption, and GPU VRAM requirements. 8.2.2 Analysis of the extended avian dataset Figure S3 presents the species tree inferred by STELAR-X on the extended avian dataset comprising 363 taxa and 63,430 genes (intergenic loci). STELAR-X accurately reconstructs major phylogenetic groupings The extended avian dataset comprises 363 taxa spanning 218 families, 37 orders, and 12 major clades [ 1 ]. STELAR-X successfully reconstructed all 218 families and all 37 orders. At the clade level, it correctly recovered 11 out of the 12 major clades, including Columbimorphae, Mirandornithes, Cursorimorphae, Aequornithes, Phaethontimorphae, Afroaves, and Australaves. The only incorrectly reconstructed clade was Otidimorphae: Musophagiformes was placed as sister to Strisores, distant from Otidiformes and Cuculiformes. Table S5 presents the reconstruction performance across the 12 clades. View this table: View inline View popup Download powerpoint Table S4: Comparison of running time and memory usage between STELAR-X and ASTRAL-MP on biological datasets Download figure Open in new tab Figure S3: Species tree estimated by STELAR-X on the extended avian dataset with 363 taxa and 63,430 genes (intergenic loci). Although the gene trees were highly incomplete, we did not augment the set of subtree bipartitions in the gene trees by adding extra subtree-bipartitions, as our primary objective here is to demonstrate scalability. View this table: View inline View popup Download powerpoint Table S5: Recovery of major avian clades by STELAR-X on the extended avian dataset of 363 taxa. Mirandornithes placed as sister to Columbimorphae While the previous study [ 2 ] placed Mirandornithes as sister to Columbimorphae within Columbea, the study on the 363 taxa extended avian dataset by [ 1 ] placed Mirandornithes as sister to all other living birds (Neoaves). Interestingly, STELAR-X recovers the same previous relationship placing Mirandornithes and Columbimorphae as sisters while analyzing the extended avian dataset. They together, however are sister to all other living birds. Waterbirds are placed deep within a separate clade Unlike some previous studies [ 2 , 3 ] that placed waterbirds (Aequornithes and Phaethontimorphae) as sister to landbirds, the published tree corresponding to the extended avian dataset [ 1 ] placed waterbirds deep within a diverse clade. STELAR-X also reconstructed the same relationship placing waterbirds placing waterbirds with Strisores, Cursorimorphae, and Opisthocomiformes. Australaves and Afroaves are placed as sister clades to form Telluraves STELAR-X places Australaves and Afroaves as sisters to form Telluraves supporting the original study in [ 1 ] and previous studies [ 2 , 3 ] in contrast to the trees reported in [ 4 , 5 ]. Strigiformes and Accipitriformes are placed as sisters within Afroaves While concatenated analyses in [ 1 ] placed Accipitriformes alone as a sister to other Afroaves, the ASTRAL-MP inferred tree reported in [ 1 ] placed them as sister clades. STELAR-X also supported this grouping of Strigiformes and Accipitriformes within Afroaves with moderate support (71%). STELAR-X, however, places Colliformes as sister to all other Afroaves, in contrast to [ 1 ] which places Colliformes deeper within Afroaves. Rheiformes is grouped with Tinamiformes within Palaeognathae In the original study on the extended avian dataset [ 1 ], ASTRAL-MP places Rheiformes as a sister to Tinamiformes, in contrast to the study in [ 6 ] which placed Rheiformes as a sister to (Apterygiformes+Casuariiformes). STELAR-X also recovered the same relationship placing Rheiformes as sister to Tinamiformes within the clade Palaeognathae. 9 Additional Results on Simulated Datasets 9.1 Additional Results on Scalability on Simulated Datasets We report the comparison of running time and memory usage of STELAR-X, ASTRAL-MP, ASTER, WQFM-TREE, and TMC for the simulated datasets of 37, 100, 200, and 500 taxa in Table S6 . The results are averaged over 10 replicates for each setting except that we could not run TMC on the 500-taxon dataset due to its high computational demands. We present the running time and memory consumption of STELAR-X, ASTRAL-MP, ASTER, WQFM-TREE, and TMC on simulated datasets with 37, 100, 200, and 500 taxa in Table S6 . For each setting, we report results averaged over 10 replicates. Due to its substantial computational requirements, TMC could not be executed on the 500-taxon dataset. View this table: View inline View popup Download powerpoint Table S6: Comparison of running time and memory usage of STELAR-X, ASTRAL-MP, ASTER, WQFM-TREE, and TMC for our simulated datasets of 37, 100, 200, and 500 taxa averaged over 10 replicates (except for the 500-taxon dataset where we could not run TMC due to its high computational demands.) 9.2 Additional Results on Scalability on True and Estimated Gene Trees To further assess the scalability of STELAR-X on estimated gene trees, we analyze three simulated datasets analyzed in prior studies. Two datasets contain 500 and 1,000 taxa, respectively, each with 1,000 genes. These datasets were previously analyzed in the ASTRAL-II [ 7 ] and later re-analyzed in the WQFM-TREE study [ 8 ]. The species trees in these datasets were generated under a Yule process with maximum tree length = 2M and speciation rate = 1 × 10 −6 . In addition, we include a larger dataset from the ASTRAL-MP study [ 9 ], comprising 10,000 taxa and 1,000 gene trees simulated with SimPhy under the multi-species coalescent model. For all three datasets, we evaluate STELAR-X and ASTRAL-MP using both the true gene trees and the corresponding estimated gene trees. Table S7 summarizes the running time, CPU RAM usage, and GPU VRAM usage of both methods across these settings. 9.3 Additional Results on Accuracy on Simulated Datasets Figure S4 presents the comparison of the accuracy of STELAR-X, ASTRAL-MP, WQFM-TREE, ASTER, and TMC averaged over 10 replicates on simulated datasets of 37, 100, 200, and 500 taxa datasets. We could not run TMC on 500-taxon dataset due to its high computational demands. View this table: View inline View popup Download powerpoint Table S7: Comparison of running time and memory usage between STELAR-X and ASTRAL-MP for true vs. estimated trees in simulated datasets averaged over 10 replicates Download figure Open in new tab Figure S4: (a)-(c) Average RF rates of STELAR-X, ASTRAL-MP, WQFM-TREE, ASTER, and TMC over 10 replicates (a) varying ILS (b) varying sequence lengths (37 taxa) (c) 100–500 taxa (except that we could not run TMC on 500-taxon dataset due to its high computational demands.) Footnotes Scalability results updated to include a comprehensive comparison with ASTER; Experimental results added for scalability on true and estimated gene trees; Triplet MaxCut (TMC) added as a benchmark for accuracy evaluation; Detailed results on the reconstruction accuracy of the extended avian dataset presented in main and supplementary material References [1]. ↵ Erich D Jarvis , Siavash Mirarab , Andre J Aberer , Bo Li , Peter Houde , Cai Li , Simon YW Ho , Brant C Faircloth , Benoit Nabholz , Jason T Howard , et al. Whole-genome analyses resolve early branches in the tree of life of modern birds . Science , 346 ( 6215 ): 1320 – 1331 , 2014 . OpenUrl Abstract / FREE Full Text [2]. ↵ Norman J Wickett , Siavash Mirarab , Nam Nguyen , Tandy Warnow , Eric Carpenter , Naim Matasci , Saravanaraj Ayyampalayam , Michael S Barker , J Gordon Burleigh , Matthew A Gitzendanner , et al. Phylotranscriptomic analysis of the origin and early diversification of land plants . Proceedings of the National Academy of Sciences , 111 ( 45 ): E4859 – E4868 , 2014 . OpenUrl Abstract / FREE Full Text [3]. ↵ R. R. Hudson . Testing the constant-rate neutral allele model with protein sequence data . Evolution , 37 : 203 – 217 , 1983 . OpenUrl CrossRef PubMed Web of Science [4]. ↵ H. Gershowitz , D. L. Rucknagel , and R. E. Tashian M. Nei . Stochastic errors in dna evolution and molecular phylogeny . In In H. Gershowitz , D. L. Rucknagel , and R. E. Tashian , editors, Evolutionary Perspectives and the New Genetics , pages 133 – 147 , 1986 . [5]. ↵ M. Nei . Molecular evolutionary genetics . New York , 1987 . Columbia University Press . [6]. ↵ N. Rosenberg . The Probability of Topological Concordance of Gene Trees and Species Trees . Theoretical Population Biology , 61 ( 2 ): 225 – 247 , March 2002 . OpenUrl CrossRef PubMed Web of Science [7]. ↵ Sebastien Roch and Mike Steel . Likelihood-based tree reconstruction on a concatenation of aligned sequence data sets can be statistically inconsistent . Theoretical Population Biology , 100 : 56 – 62 , 2015 . OpenUrl CrossRef [8]. ↵ J H Degnan , M DeGiorgio , D Bryant , and N A Rosenberg . Properties of consensus methods for inferring species trees from gene trees . Systematic Biology , 58 : 35 – 54 , 2009 . OpenUrl CrossRef PubMed Web of Science [9]. ↵ L S Kubatko and J H Degnan . Inconsistency of phylogenetic estimates from concatenated data under coalescence . Systematic Biology , 56 : 17 , 2007 . OpenUrl CrossRef PubMed Web of Science [10]. ↵ J Heled and A J Drummond . Bayesian inference of species trees from multilocus data . Molecular Biology and Evolution , 27 : 570 – 580 , 2010 . OpenUrl CrossRef PubMed Web of Science [11]. A.J. Drummond and A. Rambaut . BEAST: Bayesian evolutionary analysis by sampling trees . BMC Evolutionary Biology , 7 : 214 , 2007 . OpenUrl PubMed [12]. L Liu . BEST: Bayesian estimation of species trees under the coalescent model . Bioinformatics , 24 : 2542 – 2543 , 2008 . OpenUrl CrossRef PubMed Web of Science [13]. ↵ Julia Chifman and Laura Kubatko . Quartet from snp data under the coalescent model . Bioinformatics , 30 ( 23 ): 3317 – 3324 , 2014 . OpenUrl CrossRef PubMed Web of Science [14]. ↵ Liang Liu , Lili Yu , and Scott V Edwards . A maximum pseudo-likelihood approach for estimating species trees under the coalescent model . BMC Evolutionary Biology , 10 : 302 , 2010 . OpenUrl PubMed [15]. ↵ Siavash Mirarab , Rezwana Reaz , Md S Bayzid , Théo Zimmermann , M Shel Swenson , and Tandy Warnow . ASTRAL: genome-scale coalescent-based species tree estimation . Bioinformatics , 30 ( 17 ): i541 – i548 , 2014 . OpenUrl CrossRef PubMed Web of Science [16]. ↵ B Larget , S K Kotha , C N Dewey , and C Ané . BUCKy: Gene tree/species tree reconciliation with the Bayesian concordance analysis . Bioinformatics , 26 ( 22 ): 2910 – 2911 , 2010 . OpenUrl CrossRef PubMed Web of Science [17]. ↵ E Mossel and S Roch . Incomplete lineage sorting: consistent phylogeny estimation from multiple loci . IEEE/ACM Transactions on Computational Biology and Bioinformatics , 7 ( 1 ): 166 – 171 , 2011 . OpenUrl [18]. ↵ L S Kubatko , B C Carstens , and L L Knowles . Stem: Species tree estimation using maximum likelihood for gene trees under coalescence . Bioinformatics , 25 : 971 – 973 , 2009 . OpenUrl CrossRef PubMed Web of Science [19]. ↵ Liang Liu , Lili Yu , Dennis K Pearl , and Scott V Edwards . Estimating species phylogenies using coalescence times among sequences . Systematic Biology , 58 ( 5 ): 468 – 477 , 2009 . OpenUrl CrossRef PubMed [20]. ↵ Liang Liu and Lili Yu . Estimating species trees from unrooted gene trees . Systematic Biology , 60 ( 5 ): 661 – 667 , 2011 . OpenUrl CrossRef PubMed [21]. ↵ Pranjal Vachaspati and Tandy Warnow . Astrid: accurate species trees from internode distances . BMC Genomics , 16 ( 10 ): S3 , 2015 . OpenUrl CrossRef [22]. ↵ Mazharul Islam , Kowshika Sarker , Trisha Das , Rezwana Reaz , and Md Shamsuzzoha Bayzid . Stelar: A statistically consistent coalescent-based species tree estimation method by maximizing triplet consistency . BMC Genomics , 21 ( 1 ): 1 – 13 , 2020 . OpenUrl CrossRef PubMed [23]. ↵ John Yin , Chao Zhang , and Siavash Mirarab . ASTRAL-MP: scaling ASTRAL to very large datasets using randomization and parallelization . Bioinformatics , 35 ( 20 ): 3961 – 3969 , 2019 . OpenUrl CrossRef PubMed [24]. ↵ Md Shamsuzzoha Bayzid , Tyler Hunt , and Tandy Warnow . Disk covering methods improve phylogenomic analyses . BMC Genomics , 15 ( 6 ): S7 , 2014 . OpenUrl CrossRef [25]. ↵ Metin Balaban , Yueyu Jiang , Qiyun Zhu , Daniel McDonald , Rob Knight , and Siavash Mirarab . Generation of accurate, expandable phylogenomic trees with udance . Nature biotechnology , 42 ( 5 ): 768 – 777 , 2024 . OpenUrl PubMed [26]. ↵ M. S. Bayzid , S. Mirarab , and T. Warnow . Inferring optimal species trees under gene duplication and loss . In Proc. of Pacific Symposium on Biocomputing (PSB) , volume 18 , pages 250 – 261 , 2013 . OpenUrl [27]. ↵ Xinyao Yi . A study of performance programming of cpu, gpu accelerated computers and simd architecture . ArXiv , abs/2409.10661, 2024 . [28]. ↵ Chao Zhang , Rasmus Nielsen , and Siavash Mirarab . Aster: A package for large-scale phylogenomic reconstructions . Molecular Biology and Evolution , 42 ( 8 ): msaf172 , 07 2025 . OpenUrl PubMed [29]. ↵ Abdur Rafi , Ahmed Mahir Sultan Rumi , Sheikh Azizul Hakim , Sohaib , Md Toki Tahmid , Rabib Jahin Ibn Momin , Tanjeem Azwad Zaman , Rezwana Reaz , and Md Shamsuzzoha Bayzid . wqfm-tree: highly accurate and scalable quartet-based species tree inference from gene trees . Bioinformatics Advances , 5 ( 1 ): vbaf053 , 2025 . OpenUrl CrossRef [30]. ↵ Gur Sevillya , Zeev Frenkel , and Sagi Snir . Triplet maxcut: a new toolkit for rooted supertree . Methods in Ecology and Evolution , 7 ( 11 ): 1359 – 1365 , August 2016 . OpenUrl [31]. ↵ Diego Mallo , Leonardo De Oliveira Martins , and David Posada . Simphy : Phylogenomic simulation of gene, locus, and species trees . Systematic Biology , 65 ( 2 ): 334 – 344 , 11 2015 . OpenUrl PubMed [32]. ↵ Erich D. Jarvis , Siavash Mirarab , Andre J. Aberer , Bo Li , Peter Houde , Cai Li , Simon Y. W. Ho , Brant C. Faircloth , Benoit Nabholz , Jason T. Howard , Alexander Suh , Claudia C. Weber , Rute R. da Fonseca , Jianwen Li , Fang Zhang , Hui Li , Long Zhou , Nitish Narula , Liang Liu , Ganesh Ganapathy , Bastien Boussau , Md. Shamsuzzoha Bayzid , Volodymyr Zavidovych , Sankar Subramanian , Toni Gabaldón, Salvador Capella-Gutiérrez, Jaime Huerta-Cepas , Bhanu Rekepalli , Kasper Munch , Mikkel Schierup , Bent Lindow , Wesley C. Warren , David Ray , Richard E. Green , Michael W. Bruford , Xiangjiang Zhan , Andrew Dixon , Shengbin Li , Ning Li , Yinhua Huang , Elizabeth P. Derryberry , Mads Frost Bertelsen , Frederick H. Sheldon , Robb T. Brumfield , Claudio V. Mello , Peter V. Lovell , Morgan Wirthlin , Maria Paula Cruz Schneider , Francisco Prosdocimi , José Alfredo Samaniego , Amhed Missael Vargas Velazquez , Alonzo Alfaro-Núñez , Paula F. Campos , Bent Petersen , Thomas Sicheritz-Ponten , An Pas , Tom Bailey , Paul Scofield , Michael Bunce , David M. Lambert , Qi Zhou , Polina Perelman , Amy C. Driskell , Beth Shapiro , Zijun Xiong , Yongli Zeng , Shiping Liu , Zhenyu Li , Binghang Liu , Kui Wu , Jin Xiao , Xiong Yinqi , Qiuemei Zheng , Yong Zhang , Huanming Yang , Jian Wang , Linnea Smeds , Frank E. Rheindt , Michael Braun , Jon Fjeldsa , Ludovic Orlando , F. Keith Barker , Knud Andreas Jønsson , Warren Johnson , Klaus-Peter Koepfli , Stephen O’Brien , David Haussler , Oliver A. Ryder , Carsten Rahbek , Eske Willerslev , Gary R. Graves , Travis C. Glenn , John McCormack , Dave Burt , Hans Ellegren , Per Alström , Scott V. Edwards , Alexandros Stamatakis , David P. Mindell , Joel Cracraft , Edward L. Braun , Tandy Warnow , Wang Jun , M. Thomas P. Gilbert , and Guojie Zhang . Whole-genome analyses resolve early branches in the tree of life of modern birds . Science , 346 ( 6215 ): 1320 – 1331 , December 2014 . OpenUrl Abstract / FREE Full Text [33]. ↵ Josefin Stiller , Shaohong Feng , Al-Aabid Chowdhury , Iker Rivas-González , David A. Duchêne , Qi Fang , Yuan Deng , Alexey Kozlov , Alexandros Stamatakis , Santiago Claramunt , Jacqueline M. T. Nguyen , Simon Y. W. Ho , Brant C. Faircloth , Julia Haag , Peter Houde , Joel Cracraft , Metin Balaban , Uyen Mai , Guangji Chen , Rongsheng Gao , Chengran Zhou , Yulong Xie , Zijian Huang , Zhen Cao , Zhi Yan , Huw A. Ogilvie , Luay Nakhleh , Bent Lindow , Benoit Morel , Jon Fjeldså , Peter A. Hosner , Rute R. da Fonseca , Bent Petersen , Joseph A. Tobias , Tamás Székely , Jonathan David Kennedy , Andrew Hart Reeve , Andras Liker , Martin Stervander , Agostinho Antunes , Dieter Thomas Tietze , Mads F. Bertelsen , Fumin Lei , Carsten Rahbek , Gary R. Graves , Mikkel H. Schierup , Tandy Warnow , Edward L. Braun , M. Thomas P. Gilbert , Erich D. Jarvis , Siavash Mirarab , and Guojie Zhang . Complexity of avian evolution revealed by family-level genomes . Nature , 629 ( 8013 ): 851 – 860 , April 2024 . OpenUrl CrossRef PubMed [34]. ↵ Siavash Mirarab , Md Shamsuzzoha Bayzid , Bastien Boussau , and Tandy Warnow . Statistical binning enables an accurate coalescent-based estimation of the avian tree . Science , 346 ( 6215 ): 1250463 , 2014 . OpenUrl Abstract / FREE Full Text [35]. ↵ Erfan Sayyari and Siavash Mirarab . Fast coalescent-based computation of local branch support from quartet frequencies . Molecular Biology and Evolution , 33 ( 7 ): 1654 – 1668 , 04 2016 . OpenUrl CrossRef PubMed [36]. ↵ Alexandre R. Zuntini , Tom Carruthers , Olivier Maurin , Paul C. Bailey , Kevin Leempoel , Grace E. Brewer , Niroshini Epitawalage , Elaine Françoso , Berta Gallego-Paramo , Catherine McGinnie , Raquel Negrão , Shyamali R. Roy , Lalita Simpson , Eduardo Toledo Romero , Vanessa M. A. Barber , Laura Botigué , James J. Clarkson , Robyn S. Cowan , Steven Dodsworth , Matthew G. Johnson , Jan T. Kim , Lisa Pokorny , Norman J. Wickett , Guilherme M. Antar , Lucinda DeBolt , Karime Gutierrez , Kasper P. Hendriks , Alina Hoewener , Ai-Qun Hu , Elizabeth M. Joyce , Izai A. B. S. Kikuchi , Isabel Larridon , Drew A. Larson , Elton John de Lírio , Jing-Xia Liu , Panagiota Malakasi , Natalia A. S. Przelomska , Toral Shah , Juan Viruel , Theodore R. Allnutt , Gabriel K. Ameka , Rose L. Andrew , Marc S. Appelhans , Montserrat Arista , María Jesús Ariza , Juan Arroyo , Watchara Arthan , Julien B. Bachelier , C. Donovan Bailey , Helen F. Barnes , Matthew D. Barrett , Russell L. Barrett , Randall J. Bayer , Michael J. Bayly , Ed Biffin , Nicky Biggs , Joanne L. Birch , Diego Bogarín , Renata Borosova , Alexander M. C. Bowles , Peter C. Boyce , Gemma L. C. Bramley , Marie Briggs , Linda Broadhurst , Gillian K. Brown , Jeremy J. Bruhl , Anne Bruneau , Sven Buerki , Edie Burns , Margaret Byrne , Stuart Cable , Ainsley Calladine , Martin W. Callmander , Ángela Cano , David J. Cantrill , Warren M. Cardinal-McTeague , Mónica M. Carlsen , Abigail J. A. Carruthers , Alejandra de Castro Mateo , Mark W. Chase , Lars W. Chatrou , Martin Cheek , Shilin Chen , Maarten J. M. Christenhusz , Pascal-Antoine Christin , Mark A. Clements , Skye C. Coffey , John G. Conran , Xavier Cornejo , Thomas L. P. Couvreur , Ian D. Cowie , Laszlo Csiba , Iain Darbyshire , Gerrit Davidse , Nina M. J. Davies , Aaron P. Davis , Kor-jent van Dijk , Stephen R. Downie , Marco F. Duretto , Melvin R. Duvall , Sara L. Edwards , Urs Eggli , Roy H. J. Erkens , Marcial Escudero , Manuel de la Estrella , Federico Fabriani , Michael F. Fay , Paola de L. Ferreira , Sarah Z. Ficinski , Rachael M. Fowler , Sue Frisby , Lin Fu , Tim Fulcher , Mercè Galbany-Casals , Elliot M. Gardner , Dmitry A. German , Augusto Giaretta , Marc Gibernau , Lynn J. Gillespie , Cynthia C. González , David J. Goyder , Sean W. Graham , Aurélie Grall , Laura Green , Bee F. Gunn , Diego G. Gutiérrez , Jan Hackel , Thomas Haevermans , Anna Haigh , Jocelyn C. Hall , Tony Hall , Melissa J. Harrison , Sebastian A. Hatt , Oriane Hidalgo , Trevor R. Hodkinson , Gareth D. Holmes , Helen C. F. Hopkins , Christopher J. Jackson , Shelley A. James , Richard W. Jobson , Gudrun Kadereit , Imalka M. Kahandawala , Kent Kainulainen , Masahiro Kato , Elizabeth A. Kellogg , Graham J. King , Beata Klejevskaja , Bente B. Klitgaard , Ronell R. Klopper , Sandra Knapp , Marcus A. Koch , James H. Leebens-Mack , Frederic Lens , Christine J. Leon , Étienne Léveillé-Bourret , Gwilym P. Lewis , De-Zhu Li , Lan Li , Sigrid Liede-Schumann , Tatyana Livshultz , David Lorence , Meng Lu , Patricia Lu-Irving , Jaquelini Luber , Eve J. Lucas , Manuel Luján , Mabel Lum , Terry D. Macfarlane , Carlos Magdalena , Vidal F. Mansano , Lizo E. Masters , Simon J. Mayo , Kristina McColl , Angela J. McDonnell , Andrew E. McDougall , Todd G. B. McLay , Hannah McPherson , Rosa I. Meneses , Vincent S. F. T. Merckx , Fabián A. Michelangeli , John D. Mitchell , Alexandre K. Monro , Michael J. Moore , Taryn L. Mueller , Klaus Mummenhoff , Jérôme Munzinger , Priscilla Muriel , Daniel J. Murphy , Katharina Nargar , Lars Nauheimer , Francis J. Nge , Reto Nyffeler , Andrés Orejuela , Edgardo M. Ortiz , Luis Palazzesi , Ariane Luna Peixoto , Susan K. Pell , Jaume Pellicer , Darin S. Penneys , Oscar A. Perez-Escobar , Claes Persson , Marc Pignal , Yohan Pillon , José R. Pirani , Gregory M. Plunkett , Robyn F. Powell , Ghillean T. Prance , Carmen Puglisi , Ming Qin , Richard K. Rabeler , Paul E. J. Rees , Matthew Renner , Eric H. Roalson , Michele Rodda , Zachary S. Rogers , Saba Rokni , Rolf Rutishauser , Miguel F. de Salas , Hanno Schaefer , Rowan J. Schley , Alexander Schmidt-Lebuhn , Alison Shapcott , Ihsan Al-Shehbaz , Kelly A. Shepherd , Mark P. Simmons , André O. Simões , Ana Rita G. Simões , Michelle Siros , Eric C. Smidt , James F. Smith , Neil Snow , Douglas E. Soltis , Pamela S. Soltis , Robert J. Soreng , Cynthia A. Sothers , Julian R. Starr , Peter F. Stevens , Shannon C. K. Straub , Lena Struwe , Jennifer M. Taylor , Ian R. H. Telford , Andrew H. Thornhill , Ifeanna Tooth , Anna Trias-Blasi , Frank Udovicic , Timothy M. A. Utteridge , Jose C. Del Valle , G. Anthony Verboom , Helen P. Vonow , Maria S. Vorontsova , Jurriaan M. de Vos , Noor Al-Wattar , Michelle Waycott , Cassiano A. D. Welker , Adam J. White , Jan J. Wieringa , Luis T. Williamson , Trevor C. Wilson , Sin Yeng Wong , Lisa A. Woods , Roseina Woods , Stuart Worboys , Martin Xanthos , Ya Yang , Yu-Xiao Zhang , Meng-Yuan Zhou , Sue Zmarzty , Fernando O. Zuloaga , Alexandre Antonelli , Sidonie Bellot , Darren M. Crayn , Olwen M. Grace , Paul J. Kersey , Ilia J. Leitch , Hervé Sauquet , Stephen A. Smith , Wolf L. Eiserhardt , Félix Forest , and William J. Baker . Phylogenomics and the rise of the angiosperms . Nature , 629 ( 8013 ): 843 – 850 , April 2024 . OpenUrl CrossRef PubMed [37]. ↵ William J Baker , Paul Bailey , Vanessa Barber , Abigail Barker , Sidonie Bellot , David Bishop , Laura R Botigué , Grace Brewer , Tom Carruthers , James J Clarkson , et al. A comprehensive phylogenomic platform for exploring the angiosperm tree of life . Systematic biology , 71 ( 2 ): 301 – 319 , 2022 . OpenUrl CrossRef PubMed References [1]. Josefin Stiller , Shaohong Feng , Al-Aabid Chowdhury , Iker Rivas-González , David A. Duchêne , Qi Fang , Yuan Deng , Alexey Kozlov , Alexandros Stamatakis , Santiago Claramunt , Jacqueline M. T. Nguyen , Simon Y. W. Ho , Brant C. Faircloth , Julia Haag , Peter Houde , Joel Cracraft , Metin Balaban , Uyen Mai , Guangji Chen , Rongsheng Gao , Chengran Zhou , Yulong Xie , Zijian Huang , Zhen Cao , Zhi Yan , Huw A. Ogilvie , Luay Nakhleh , Bent Lindow , Benoit Morel , Jon Fjeldså , Peter A. Hosner , Rute R. da Fonseca , Bent Petersen , Joseph A. Tobias , Tamás Székely , Jonathan David Kennedy , Andrew Hart Reeve , Andras Liker , Martin Stervander , Agostinho Antunes , Dieter Thomas Tietze , Mads F. Bertelsen , Fumin Lei , Carsten Rahbek , Gary R. Graves , Mikkel H. Schierup , Tandy Warnow , Edward L. Braun , M. Thomas P. Gilbert , Erich D. Jarvis , Siavash Mirarab , and Guojie Zhang . Complexity of avian evolution revealed by family-level genomes . Nature , 629 ( 8013 ): 851 – 860 , April 2024 . OpenUrl CrossRef PubMed [2]. Erich D. Jarvis , Siavash Mirarab , Andre J. Aberer , Bo Li , Peter Houde , Cai Li , Simon Y. W. Ho , Brant C. Faircloth , Benoit Nabholz , Jason T. Howard , Alexander Suh , Claudia C. Weber , Rute R. da Fonseca , Jianwen Li , Fang Zhang , Hui Li , Long Zhou , Nitish Narula , Liang Liu , Ganesh Ganapathy , Bastien Boussau , Md. Shamsuzzoha Bayzid , Volodymyr Zavidovych , Sankar Subramanian , Toni Gabaldón , Salvador Capella-Gutiérrez , Jaime Huerta-Cepas , Bhanu Rekepalli , Kasper Munch , Mikkel Schierup , Bent Lindow , Wesley C. Warren , David Ray , Richard E. Green , Michael W. Bruford , Xiangjiang Zhan , Andrew Dixon , Shengbin Li , Ning Li , Yinhua Huang , Elizabeth P. Derryberry , Mads Frost Bertelsen , Frederick H. Sheldon , Robb T. Brumfield , Claudio V. Mello , Peter V. Lovell , Morgan Wirthlin , Maria Paula Cruz Schneider , Francisco Prosdocimi , José Alfredo Samaniego , Amhed Missael Vargas Velazquez , Alonzo Alfaro-Núñez , Paula F. Campos , Bent Petersen , Thomas Sicheritz-Ponten , An Pas , Tom Bailey , Paul Scofield , Michael Bunce , David M. Lambert , Qi Zhou , Polina Perelman , Amy C. Driskell , Beth Shapiro , Zijun Xiong , Yongli Zeng , Shiping Liu , Zhenyu Li , Binghang Liu , Kui Wu , Jin Xiao , Xiong Yinqi , Qiuemei Zheng , Yong Zhang , Huanming Yang , Jian Wang , Linnea Smeds , Frank E. Rheindt , Michael Braun , Jon Fjeldsa , Ludovic Orlando , F. Keith Barker , Knud Andreas Jønsson , Warren Johnson , Klaus-Peter Koepfli , Stephen O’Brien , David Haussler , Oliver A. Ryder , Carsten Rahbek , Eske Willerslev , Gary R. Graves , Travis C. Glenn , John McCormack , Dave Burt , Hans Ellegren , Per Alström , Scott V. Edwards , Alexandros Stamatakis , David P. Mindell , Joel Cracraft , Edward L. Braun , Tandy Warnow , Wang Jun , M. Thomas P. Gilbert , and Guojie Zhang . Whole-genome analyses resolve early branches in the tree of life of modern birds . Science , 346 ( 6215 ): 1320 – 1331 , December 2014 . OpenUrl Abstract / FREE Full Text [3]. Heiner Kuhl , Carolina Frankl-Vilches , Antje Bakker , Gerald Mayr , Gerhard Nikolaus , Stefan T Boerno , Sven Klages , Bernd Timmermann , and Manfred Gahr . An unbiased molecular approach using 3-utrs resolves the avian family-level tree of life . Molecular Biology and Evolution , 38 ( 1 ): 108 – 127 , November 2020 . OpenUrl [4]. Richard O. Prum , Jacob S. Berv , Alex Dornburg , Daniel J. Field , Jeffrey P. Townsend , Emily Moriarty Lemmon , and Alan R. Lemmon . A comprehensive phylogeny of birds (aves) using targeted next-generation dna sequencing . Nature , 526 ( 7574 ): 569 – 573 , October 2015 . OpenUrl CrossRef PubMed [5]. Shaoyuan Wu , Frank E. Rheindt , Jin Zhang , Jiajia Wang , Lei Zhang , Cheng Quan , Zhiheng Li , Min Wang , Feixiang Wu , Yanhua Qu , Scott V. Edwards , Zhonghe Zhou , and Liang Liu . Genomes, fossils, and the concurrent rise of modern birds and flowering plants in the late cretaceous . Proceedings of the National Academy of Sciences , 121 ( 8 ), February 2024 . [6]. Alison Cloutier , Timothy B Sackton , Phil Grayson , Michele Clamp , Allan J Baker , and Scott V Edwards . Whole-genome analyses resolve the phylogeny of flightless birds (palaeognathae) in the presence of an empirical anomaly zone . Systematic Biology , 68 ( 6 ): 937 – 955 , April 2019 . OpenUrl CrossRef PubMed [7]. Siavash Mirarab and Tandy Warnow . Astral-ii: coalescent-based species tree estimation with many hundreds of taxa and thousands of genes . Bioinformatics , 31 ( 12 ): i44 – i52 , June 2015 . OpenUrl CrossRef PubMed [8]. Abdur Rafi , Ahmed Mahir Sultan Rumi , Sheikh Azizul Hakim , Sohaib , Md Toki Tahmid , Rabib Jahin Ibn Momin , Tanjeem Azwad Zaman , Rezwana Reaz , and Md Shamsuzzoha Bayzid . wqfm-tree: highly accurate and scalable quartet-based species tree inference from gene trees . Bioinformatics Advances , 5 ( 1 ): vbaf053 , 2025 . OpenUrl CrossRef [9]. John Yin , Chao Zhang , and Siavash Mirarab . ASTRAL-MP: scaling ASTRAL to very large datasets using randomization and parallelization . Bioinformatics , 35 ( 20 ): 3961 – 3969 , 2019 . OpenUrl CrossRef PubMed View the discussion thread. Back to top Previous Next Posted February 22, 2026. Download PDF Email Thank you for your interest in spreading the word about bioRxiv. NOTE: Your email address is requested solely to identify you as the sender of this article. Your Email * Your Name * Send To * Enter multiple addresses on separate lines or separate them with commas. You are going to email the following STELAR-X: Scaling Coalescent-Based Species Tree Inference to 100,000 Species and Beyond Message Subject (Your Name) has forwarded a page to you from bioRxiv Message Body (Your Name) thought you would like to see this page from the bioRxiv website. Your Personal Message CAPTCHA This question is for testing whether or not you are a human visitor and to prevent automated spam submissions. Share STELAR-X: Scaling Coalescent-Based Species Tree Inference to 100,000 Species and Beyond Anik Saha , Md. Shamsuzzoha Bayzid bioRxiv 2025.11.22.689894; doi: https://doi.org/10.1101/2025.11.22.689894 Share This Article: Copy Citation Tools STELAR-X: Scaling Coalescent-Based Species Tree Inference to 100,000 Species and Beyond Anik Saha , Md. Shamsuzzoha Bayzid bioRxiv 2025.11.22.689894; doi: https://doi.org/10.1101/2025.11.22.689894 Citation Manager Formats BibTeX Bookends EasyBib EndNote (tagged) EndNote 8 (xml) Medlars Mendeley Papers RefWorks Tagged Ref Manager RIS Zotero Tweet Widget Facebook Like Google Plus One Subject Area Bioinformatics Subject Areas All Articles Animal Behavior and Cognition (7618) Biochemistry (17633) Bioengineering (13857) Bioinformatics (41841) Biophysics (21399) Cancer Biology (18529) Cell Biology (25422) Clinical Trials (138) Developmental Biology (13352) Ecology (19860) Epidemiology (2067) Evolutionary Biology (24282) Genetics (15582) Genomics (22462) Immunology (17700) Microbiology (40295) Molecular Biology (17140) Neuroscience (88421) Paleontology (666) Pathology (2823) Pharmacology and Toxicology (4813) Physiology (7632) Plant Biology (15107) Scientific Communication and Education (2042) Synthetic Biology (4284) Systems Biology (9808) Zoology (2267)