MEGA12: Molecular Evolutionary Genetic Analysis Version 12 for Adaptive and Green Computing

1The Molecular Evolutionary Genetics Analysis (MEGA) software is extensively used for molecular evolution and phylogenetics. It offers many computational tools, including maximum likelihood (ML), maximum parsimony (MP), ordinary least squares, Bayesian, and distance-based methods (Fig. 1). Some popular functionalities in MEGA are the selection of optimal nucleotide and amino acid substitution models, inference of evolutionary relationships, tests of phylogenies using the bootstrap method, estimation of sequence divergences and times, and the reconstruction of ancestral sequences (supplementary fig. S1, Supplementary Material online).

2Notably, phylogenetic ML analyses are time-consuming and contribute to a substantial carbon footprint. To tackle these challenges, the latest update of MEGA has aimed to improve the computational efficiency of ML analyses. This has been achieved by developing and implementing heuristic approaches that avoid unnecessary calculations while preserving accuracy. Further efficiencies are gained by optimizing parallel computations to make the best use of available computing resources. In the following sections, we will discuss these updates and enhancements to the graphical user interface (GUI), including seamless access to an external application (DrPhylo) for detecting fragile clades and associated sequences in the inferred phylogenies.

3Simulated datasets were obtained from a previously published research study. These nucleotide multiple sequence alignments (MSAs) were generated with varying sequence lengths, number of sequences, base frequencies, substitution rates, heterogeneity across sites, and proportion of invariant sites. A total of 24 models of substitutions (six base models and their +I, +G, and +I+G combinations; see main text) were used for simulating the data, with 300 datasets generated for each model scenario. From each model category, we randomly selected 10 datasets (out of 300), resulting in a total of 240 simulated datasets for model selection analysis. Sequence counts in these datasets ranged from 4 to 289, which were 186 to 18,171 sites long. We performed bootstrapping with the Adaptive option and model selection with the Filtered option. Then, we estimated their concordance by comparing results from standard bootstrap and model selection with the Full option, respectively.

4We also analyzed amino acid sequence datasets, generated from a concatenated MSA (Chloroplast_Martin.meg). The dataset is an example dataset in MEGA12. Forty-five MSAs were generated using the protein domain boundaries from the concatenated alignment. We performed the model selection analyses for these protein domains and compared the results from the use of the Full and Filtered options.

5The DrPhylo analysis was conducted on a clade within a fungus phylogeny derived from an ML analysis of an empirical dataset comprising 1,233 protein-coding nuclear genes from 86 yeast species. This clade was selected because it was reported to be fragile in previous research studies. The ML tree and MSAs for each protein-coding gene were obtained from.

6We used MEGA12 for all analyses to directly compare the impact of certain new features while keeping all other aspects the same because many incremental changes and bug fixes have been made over the 3 years since MEGA11 was released. For the model selection analysis, we first selected the best-fit substitution models using the Full option, which tested all the substitution models. The best-fit models found in these analyses were used as ground truth for model selection results obtained using the Filtered option. Default BIC and AICc thresholds of 5 were used in these analyses. For the bootstrap analysis, the Standard option in MEGA12 was used with 500 replicates, and the Adaptive option was used with a default standard error (SE) threshold of 5%.

7Model selection and bootstrap analyses were conducted using the command-line version of MEGA12 (“megacc”) with a single thread for direct comparisons. DrPhylo analysis was conducted using MEGA12's GUI. In all these analyses, we used a 64-bit desktop computer with 8 logical processors (3.36 GHz) and 64 GB of system memory running the Windows 10 operating system.

8Selecting the most suitable substitution model is often the initial step in molecular phylogenetics. The ML method for model selection was initially introduced in MEGA5 and has been frequently used (supplementary fig. S1, Supplementary Material online). MEGA assesses 6 primary nucleotide substitution models to determine the optimal model: general time reversible (GTR), Hasegawa–Kishino–Yano (HKY), Tamura–Nei (TN93), Tamura 3-parameter (T92), Kimura 2-parameter (K2P), and Jukes–Cantor (JC); see for a review. These primary substitution models describe the instantaneous probabilities of nucleotide substitutions at individual sites. They can be combined with a (discretized) gamma distribution of rate variation among sites (indicated by +G) and the presence/absence of invariant sites (indicated by +I), which are reviewed in.

9The computational time required for the ML analysis of 24 different model combinations increases with data size (Fig. 2a). Here, data size is quantified by multiplying the number of sequences (S) by the distinct number of site configurations (C) in the MSA. Distinct site configurations are used because all sites with the same configuration, patterns of bases present across sequences, are compressed into a single column with a corresponding frequency in the ML analysis. Due to the extensive use of model selection by a large user base of MEGA (supplementary fig. S2, Supplementary Material online), these analyses’ combined computational cost—and consequently, energy consumption—is enormous.

10To accelerate model selection, we have developed a heuristic approach that reduces the number of substitution model combinations tested, eliminating potentially suboptimal models early in the process. This new heuristic for model selection analysis of nucleotide sequence alignments begins with evaluating the ML model fit for 6 base models: GTR, HKY, TN93, T92, K2P, and JC. MEGA uses the Bayesian information criterion (BIC) and the corrected Akaike information criterion (AICc) to evaluate model fit where these criteria are calculated based on the log-likelihood fit of each model to the given MSA and its associated parameters. Therefore, MEGA first determines the BIC and AICc for these 6 base models. The base model with the lowest BIC value (BICmin) is selected first, and AICcmin is taken as the AICc value of this same model. Base models with BIC or AICc values not exceeding 5 points of BICmin or AICcmin, respectively, are considered potentially optimal models for further consideration. Models with AICc or BIC exceeding 5 points of AICcmin or BICmin are considered suboptimal, and other model combinations derived from these suboptimal base models are not tested further.

11The ML analysis of the remaining base models in combination with +I, +G (with 4 categories), and both +I+G is then carried out to calculate different information criteria for the final selection. The model with the lowest BIC is determined as the best-fit model of substitutions. MEGA outputs different information criteria scores, log likelihood (lnL), and other model parameters for models tested. In MEGA12, this heuristic can be used by selecting the newly added Filtered option (Fig. 2b). Users can also choose to set a desired threshold for BIC and AICc, with smaller threshold values resulting in the elimination of more models earlier.

12In an analysis of 240 simulated datasets generated with substitution models of various complexities in an independent study (see Materials and Methods), the Filtered option identified the same optimal substitution model as the Full analysis for 240 datasets (100% concordance). It achieved as much as 70% reduction in computational time when a complex substitution model fits the best (see Fig. 2c). The savings were lower for simpler models because simpler models are nested within more complex models, so the latter may not be eliminated early on. For this reason, the number of model combinations analyzed is directly related to the number of parameters in the best-fit model (see Fig. 2d). We anticipate that most users will experience substantial speedups by utilizing the Filtered option because complex models are often the optimal fit for bigger datasets.

13The Filtered option is also implemented for amino acid MSAs. In this case, MEGA12 first determines BIC and AICc in all 8 primary substitution models and eliminates all models with BIC and AICc values 5 more than BICmin or AICcmin, respectively, as outlined above. In the next step, BIC and AICc are computed for each of the remaining models combined with the +F option, using the empirical frequencies from the MSA. New model combinations are eliminated if their BIC and AICc exceed BICmin or AICcmin, respectively, by 5 or more. In the final step, the ML analysis of the remaining models in combination with +I, +G, and +G+I is then carried out to generate the final result.

14The use of the Filtered option for 45 chloroplast proteins (31 to 1,388 amino acids) from 10 species resulted in extensive (∼87%) savings compared with the Full analysis (see Fig. 2e). The same best-fit substitution models were found as the Full option for 43 proteins (95% concordance). A statistically indistinguishable model (ΔBIC < 10) was chosen for one of the other 2 datasets, while the second-best model was selected for the other. Model selection with the Filtered option for concatenating 45 chloroplast protein MSAs (11,039 amino acids) took only 3.7 min instead of 27.1 min for the Full analysis while producing the same substitution model.

15These results suggest that the speedup for model selection analysis will be realized for every dataset analyzed with the filtered option in MEGA12. However, the degree of computational efficiency gained depends on the complexity of the substitution model that best fits the data.

16After selecting the optimal substitution model, the next step in phylogenetic analysis is to infer evolutionary relationships and assess the confidence in the monophyly of inferred clades. The bootstrap approach has been available in MEGA since version 1 to estimate confidence in the inferred relationships. In the bootstrap procedure, many resampled MSA are generated by sampling sites with replacement until the number of sites in the resampled MSA is the same as in the original MSA. Phylogenies are inferred from these resampled MSAs using a phylogenetic tree estimation approach (e.g. ML approach). The proportion of times a cluster of sequences appears in the phylogenies obtained from the resampled MSAs is its bootstrap support (BS). A high BS value indicates that the inferred clade is statistically supported.

17Users frequently choose to generate a large number of resampled MSAs (500 to 2,000 replicates) because every BS value is an estimate whose accuracy is determined by the number of resampled MSAs analyzed. The number of bootstrap replicates increases the time required proportionally, which becomes particularly onerous for computationally intensive ML phylogenetics. To reduce this burden, MEGA12 introduces an Adaptive option for bootstrap analysis (Fig. 3a), automatically determining the optimal number of replicates for the bootstrap analysis. It is based on the fact that high BS values, which are of primary interest to researchers, can be estimated with high precision (i.e. low SE) from a small number of replicates. For example, the estimation of BS = 95% with an SE = 2.5% requires only 75 bootstrap replicates. Interestingly, BS values close to 50%, often of limited biological interest, require hundreds of replicates (390) to reach an SE of 2.5%. Therefore, using a large number of replicates primarily increases the precision of BS values close to 50%. To emphasize that the BS values are estimated with SEs, we have updated Tree Explorer in MEGA12 to display the range of BS values (±1 SE, Fig. 3b). Users have the option to display the BS value or the range calculated using the above formula. This display option is also available for phylogenies inferred using distance-based (e.g. neighbor-joining [NJ]) and MP methods.

18MEGA12's Adaptive option first generates 25 resampled MSAs. If any of the BS values in the phylogeny has an SE greater than or equal to 5%, then additional resampled MSAs are generated until all the BS values in the phylogeny have achieved an SE < 5%, a threshold that can be set by the user (Fig. 3a). Our rationale for picking a 5% default was that some of the clades in the inferred phylogeny would have BS close to 50%, so achieving an SE < 5% for these clades will require many replicates (often ∼100). With 100 replicates, the clades with high BS values will have SE closer to 2.5%. This is evident from the analysis of Drosophia_Adh.meg dataset distributed in the Examples folder with MEGA12 (Fig. 3b). MEGA12 stopped the bootstrap procedure after 87 replicates, which resulted in much narrower ranges (BS–SE to BS + SE) for high BS values than low BS values (Fig. 3b).

19We also analyzed all 240 simulated datasets with standard and adaptive bootstrap approaches. Figure 4a shows the relationship of the BS values obtained using 500 replicates (x axis) and determined adaptively (y axis) for 240 datasets. The relationship is strong (R2 = 0.99) with a slope close to 1 (Fig. 4a), i.e. the two approaches produced very similar results overall. However, there is some dispersion because we used a threshold of SE = 5% for adaptive bootstrapping. The number of replicates needed for adaptive bootstrapping varied between 25 and 124 for the 240 datasets, with 25 because of a hard lower limit placed by MEGA12. Because the default SE threshold of 5% is applied to every clade in the inferred phylogeny, the number of bootstrap replicates needed will be determined by the node whose estimated BS support is closest to 50% because the variance of a BS value (say b) is given by b(1 − b)/r, where r is the number of replicates. Indeed, there is a direct relationship between the number of replicates needed in adaptive bootstrapping and the minimum |BS − 50%| value in the inferred phylogeny in the analysis of 240 datasets (Fig. 4b). For phylogenies with uniformly high BS values (bottom right in Fig. 4b), the number of replicates needed is much smaller than when the phylogeny contains even one clade with BS value close to 50%. In any case, the Adaptive option resulted in speedups on an average of 81% times (Fig. 4c), ranging from 61% to 95% for these datasets. In general, we expect such speedups to be realized for all datasets analyzed in MEGA12, with actual computational efficiency depending on the properties of the data and the bootstrap stability of the phylogenetic inference.

20MEGA currently uses the concatenation supermatrix approach when the input contains multiple genes, domains, or genomic segments. This approach is effective in producing organismal relationships with high confidence. However, the concatenation supermatrix approach may occasionally lead to incorrect or fragile inferences with very high BS due to systematic, modeling, and data-specific biases. MEGA12 now makes available the DrPhylo approach, a sparse learning approach to identify inferred clades that may be formed due to data-specific biases. Users can launch DrPhylo analysis for any clade in the phylogeny displayed in the Tree Explorer (Fig. 5a), as well as directly from the main MEGA window (Fig. 1b). One can choose to use partitions (genes or segments) in the currently active dataset or divide the data into segments of equal length (Fig. 5b). The user may also provide a list of files, each containing a sequence alignment for a data segment, for DrPhylo analysis (Fig. 5c).

21DrPhylo is implemented in the MyESL software and linked with MEGA12 by upgrading the source code that has been previously used to link Muscle with MEGA3. MEGA12 extracts the application binaries and resources to set up the DrPhylo execution environment with the proper files, structure, and permissions when DrPhylo is run in MEGA12 for the first time after installation.

22We demonstrate the steps of DrPhylo analysis and its outputs by analyzing a phylogenetic tree of 86 fungal species inferred from the ML analysis of a concatenated sequence alignment of 1,232 genes. In this phylogeny, the placement of Ascoidea rubescens in the ML phylogeny was reported to be contentious, even though it received 100% standard BS. The clade of interest contains A. rubescens and 43 other species, which is easily disrupted by excluding just one gene. In MEGA12, the user selects the clade by clicking on the stem branch (Fig. 5a). Then, DrPhylo analysis is launched by clicking on the menu that appears (Fig. 5b) and choosing options to specify the sequence data, data type, and model grid size (Fig. 5c). We selected the dataset that was already active in MEGA and chose to display 20 top genes along with 20 taxa from the clade of interest (Fig. 5c).

23MEGA12 automatically prepares the input sources (alignments and the tree file) for a given analysis and copies them to DrPhylo's execution environment. DrPhylo is launched in a separate child process along with command-line arguments. As DrPhylo executes, MEGA captures all analysis progress information and displays it in a new progress window. When the DrPhylo process finishes, MEGA loads all of the results files into memory and adds a DrP OutputTile (Fig. 1d) to the main form to provide access to output files produced by DrPhylo (Fig. 1e). Output files include model grid (M-grid) in both graphical and textual format, position and gene sparsity score, DrPhylo run log, and options for saving or erasing results; see and for more details. Clicking on a menu item in the DrP OutputTile smartly displays the result. For example, clicking the first menu item displays the graphics file in the integrated web browser with the figure legend (Fig. 5d).

24In the grid displayed (called the model grid; M-grid), the horizontal axis represents the genes included in the model, while the vertical axis represents the species along with the classification probability for their membership within the clade of interest. The clade probability (CP) is the smallest probability of these probabilities because the most unstable member dictates the fragility of the clade. Each cell (say i,j) in the M-grid reflects the gene–species concordance (GSC) score, which quantifies the support a gene (j) provides for a species (i) within the clade of interest. Green cells indicate the gene's positive support for species membership within the clade, whereas red cells display gene–species combinations that harbor a discordant signal. Based on the GSC score, the color intensity corresponds to the strength of the concordance or discordance. provided a detailed explanation of the M-grid for this dataset.

25The M-grid in Fig. 5d shows that the CP for the clade analyzed is 0.27 due to A. rubescens receiving a low membership probability. One gene, BUSCOfEOG7W9S51, provides the strongest support for the placement of A. rubescens (green cells) in this clade, but many other genes did not support (red) this placement. Interestingly, BUSCOfEOG7W9S51 also strongly supports other species’ inclusion inside the clade. Therefore, BUSCOfEOG7W9S51 is highly influential for this clade and places A. rubescens inside it. This gene was also found using the ML approach by comparing two alternative hypotheses for the placement of A. rubescens. Removing this gene from the analysis changed the placement of A. rubescens with moderate BS. This is because of BUSCOfEOG7TN012, which shows a very high disagreement with the placement of A. rubescens in this clade (red cell, Fig. 5d) but not others. Such disagreement was confirmed in the gene tree, which positioned A. rubescens far outside the clade of interest. In summary, the availability of DrPhylo in MEGA12 will allow users to investigate fragile species relationships and causal sequences for any inferred phylogeny.

26Many users use MEGA for ML calculations of branch lengths, evolutionary parameters, ancestral states, and divergence times for a given phylogeny. These calculations can be time-consuming for larger datasets, so MEGA12 now implements fine-grained parallelization to speed up the estimation of likelihood values that are calculated independently for different sites at a given node in the phylogeny for a given set of branch lengths and substitution pattern parameter values. Our tests showed a sub-linear reduction in computational time needed, achieving slightly <50% efficiency using 4 threads compared with a single thread. A larger number of threads could offer slightly higher efficiency depending on the number of sequences, variations, and other data attributes. These sub-linear efficiency trends are explained by the fact that substantial overhead is involved in distributing calculations to different threads. In addition, more than half of the nodes in a phylogeny are terminal nodes at which only a few site configurations exist (4 or 20, except for ambiguous states for DNA or protein sequences, respectively), which are not amenable to significant savings.

27Options for automatically generating the initial tree for ML tree searching have been modified in MEGA12. When the default option is used, MEGA12 first generates two initial candidate trees: a NJ tree and a MP tree. The NJ tree is based on evolutionary distances computed using a 1-parameter substitution model for nucleotides and amino acid MSAs. To find the MP tree candidate, MEGA12 conducts 10 heuristic searches, each starting with a randomly generated tree subjected to subtree pruning and regrafting (SPR) branch swapping; see for a description. The one with the minimum tree length is chosen among the 10 MP trees. Subsequently, the log likelihood is computed for this MP tree and the NJ tree using the 1-parameter substitution model. The tree with superior log likelihood is selected as the initial tree for branch swapping to find the ML tree.

28Testing and benchmarking ML calculations using increasingly larger datasets revealed bottlenecks in the code that were not apparent when using small datasets. For instance, the initialization step to generate a map of identical site patterns was previously done in a way that was too slow for big datasets. MEGA12 makes this step orders of magnitude faster using a fast hash table. We also identified many instances of redundant initializations (e.g. site configuration maps) and calculations, which have been refactored to speed up calculations.

29The evolutionary probability (EP) analysis was introduced in MEGA11 for estimating Bayesian neutral probabilities of observing alternative alleles in a species contingent on the given species phylogeny and the MSA. The EP analysis in MEGA has been updated so that user-provided times, specified as branch lengths in a Newick tree, can be used instead of times computed using RelTime. Users can also select the focal sequence via the Analysis Preferences dialog box, which was previously restricted to the first sequence in the MSA. The results displayed for the EP calculation have been updated, and the evolutionary timespan of the base and focal sequence bases for each site are included in the output CSV file.

30The GUI has been updated extensively with many usability improvements and modifications to keep pace with computer hardware, accessories, and operating system changes.

31Tree Explorer (TE) has been enhanced by adding a quick access panel on the side toolbar to provide easy access to customization options previously accessible only through the menus (see Fig. 3b). Searching tip names has been improved to facilitate visualization and navigation through multiple matches. Users can now easily edit the names and fonts of the tip names in the phylogenetic tree, which can now be displayed with equalized branch lengths in TE or with tip names aligned vertically. Labels for internal nodes and group names can now be edited directly in TE by right-clicking a given node. Clones of the Tree Explorer and current results can now be generated, giving users snapshot copies of the current display as formatting and other edits are made to one of the copies. Finally, display settings between trees across tabs in TE have been synchronized to align tree displays visually.

32MEGA offers functionality for manual drawing and editing a phylogeny, which can help update an existing tree by adding taxa and rearranging them through drag-and-drop operations. The Tree Topology Editor in MEGA12 features several quality-of-life enhancements for manual editing of phylogenies. Users can now assign branch lengths and node heights, and they can see branch lengths and double-click to edit them on the spot, which would come in handy when Newick trees need to have branch lengths or divergence times for display or further calculations, such as EP analysis. By default, the displayed tree now automatically resizes with the window. Moving branches via drag-drop now provides visual feedback to the user. The taxon name editing text box was updated to make the behavior consistent with similar GUI elements in different operating systems.

33Responsiveness of scrolling with large datasets has been improved for the Sequence Alignment Editor (SAE), Sequence Data Explorer (SDE), and Distance Data Explorer (DDE). A taxa name search tool and highlighting of all cells corresponding to the current search match have been added for the DDE. In both the SDE and DDE, the sorting of taxa can now be by name or by distance to the first taxon. The number of base differences between the first sequence and all the remaining sequences are used in SDE. When taxa are grouped, individual taxa can be selected/unselected based on many different options: first of each group, by group size, or group inclusion.

34The user experience was severely impacted on computer monitors with ultra-high resolutions when using MEGA11. Standard graphical components (e.g. buttons, icons, and text) are rendered very small on these very high dots per inch (DPI) displays. Also, MEGA's custom visual components, such as the tree display in TE and text grids in SAE, were variously affected by changes in DPI and resolution settings. The problems were more than esthetic, causing clickable GUI components to be pushed out of view and unusable in some places. Consequently, we needed to redraw hundreds of icons in multiple resolutions and then program MEGA to automatically select the optimal resolution icon images based on the DPI of the monitor. Furthermore, we have updated all the forms and dialog boxes to auto-adjust the size and placement of components based on the monitor resolution.

35The MEGA12 GUI contains many custom forms to accommodate diverse analyses, results, and data exploration tools. In MEGA12, a Windows menu has been added to all the data and result explorers, enabling users to navigate to any other currently active windows quickly. We have also made calculation progress reporting more informative, adding analysis details, calculated parameters, and data statistics. The display of some partial results has been programmed when a user issues a command to terminate long-running processes prematurely but desires to see the results obtained thus far, such as the bootstrap analysis. Finally, we have updated the Caption Expert system introduced in MEGA4 to generate natural language descriptions of the models, methods, and parameters used in analyses. All the captions are updated for brevity and clarity. An example caption is shown for a result from DrPhylo in Fig. 4d.

36We have described numerous major upgrades implemented in MEGA12, significantly enhancing its computational efficiency and useability. We expect many phylogenetic analyses using ML methods to finish more quickly than previous versions, which is made possible by developing and implementing heuristics that avoid unnecessary computation during the selection of optimal substitution models and bootstrap tests of phylogeny. These heuristics were tested by analyzing many empirical datasets, and the results suggest that their use will generally produce the same result as this without using the heuristics. In the future, we plan to make MEGA even more computationally efficient, particularly for analyzing phylogenomic alignments on desktop computers used by many MEGA users.