The Praja family is an E3 ubiquitin ligase, promoting polyubiquitination and subsequent degradation of substrates. It comprises two paralogs, praja1 and praja2. Prior research suggests these paralogs have undergone functional divergence, with examples, such as their distinct roles in neurite outgrowth. However, the specific evolutionary trajectories of each paralog remain largely unexplored preventing mechanistic understanding of functional differences between paralogs. Here, we investigated the phylogeny and divergence of the vertebrate Praja family through molecular evolutionary analysis. Phylogenetic examination of the vertebrate praja revealed that praja1 and praja2 originated from the common ancestor of placentals via gene duplication, with praja1 evolving at twice the rate of praja2 shortly after the duplication. Moreover, a unique evolutionary trajectory for praja1 relative to other vertebrate Praja was indicated, as evidenced by principal component analysis on GC content, codon usage frequency, and amino acid composition. Subsequent motif/domain comparison revealed conserved N terminus and C terminus in praja1 and praja2, together with praja1-specific motifs, including nuclear localization signal and Ala-Gly-Ser repeats. The nuclear localization signal was demonstrated to be functional in human neuroblastoma SH-SY5Y cells using deletion mutant, while praja2 was exclusively expressed in the nucleus. These discoveries contribute to a more comprehensive understanding of the Praja family's phylogeny and suggest a functional divergence between praja1 and praja2. Specifically, the shift of praja1 into the nucleus implies the degradation of novel substrates located in the nucleus as an evolutionary consequence.

Phylogenetic trees provide insight into the evolutionary trajectories of species and molecules. However, because (2n-5)! Phylogenetic trees can be constructed from a dataset containing n sequences, but this method of phylogenetic tree construction is not ideal from the viewpoint of a combinatorial explosion to determine the optimal tree using brute force. Therefore, we developed a method for constructing a phylogenetic tree using a Fujitsu Digital Annealer, a quantum-inspired computer that solves combinatorial optimization problems at a high speed. Specifically, phylogenetic trees are generated by repeating the process of partitioning a set of sequences into two parts (i.e., the graph-cut problem). Here, the optimality of the solution (normalized cut value) obtained by the proposed method was compared with the existing methods using simulated and real data. The simulation dataset contained 32-3200 sequences, and the average branch length according to a normal distribution or the Yule model ranged from 0.125 to 0.750, covering a wide range of sequence diversity. In addition, the statistical information of the dataset is described in terms of two indices: transitivity and average p-distance. As phylogenetic tree construction methods are expected to continue to improve, we believe that this dataset can be used as a reference for comparison and confirmation of the validity of the results. Further interpretation of these analyses is explained in W. Onodera, N. Hara, S. Aoki, T. Asahi, N. Sawamura, Phylogenetic tree reconstruction via graph cut presented using a quantum-inspired computer, Mol. Phylogenet. Evol. 178 (2023) 107636.

Phylogenetic trees are essential tools in evolutionary biology that present information on evolutionary events among organisms and molecules. From a dataset of n sequences, a phylogenetic tree of (2n-5)!! possible topologies exists, and determining the optimum topology using brute force is infeasible. Recently, a recursive graph cut on a graph-represented-similarity matrix has proven accurate in reconstructing a phylogenetic tree containing distantly related sequences. However, identifying the optimum graph cut is challenging, and approximate solutions are currently utilized. Here, a phylogenetic tree was reconstructed with an improved graph cut using a quantum-inspired computer, the Fujitsu Digital Annealer (DA), and the algorithm was named the "Normalized-Minimum cut by Digital Annealer (NMcutDA) method". First, a criterion for the graph cut, the normalized cut value, was compared with existing clustering methods. Based on the cut, we verified that the simulated phylogenetic tree could be reconstructed with the highest accuracy when sequences were diverged. Moreover, for some actual data from the structure-based protein classification database, only NMcutDA could cluster sequences into correct superfamilies. Conclusively, NMcutDA reconstructed better phylogenetic trees than those using other methods by optimizing the graph cut. We anticipate that when the diversity of sequences is sufficiently high, NMcutDA can be utilized with high efficiency.