More Like this

1. Statistically Consistent Rooting of Species Trees Under the Multispecies Coalescent Model

   https://doi.org/10.1007/978-3-031-29119-7_3  

   Tabatabaee, Y.; Roch, S.; Warnow, T. (April 2023, Research in Computational Molecular Biology. RECOMB 2023. Lecture Notes in Computer Science. Springer.)

   Tang, H. (Ed.)

   Rooted species trees are used in several downstream applications of phylogenetics. Most species tree estimation methods produce unrooted trees and additional methods are then used to root these unrooted trees. Recently, Quintet Rooting (QR) (Tabatabaee et al., ISMB and Bioinformatics 2022), a polynomial-time method for rooting an unrooted species tree given unrooted gene trees under the multispecies coalescent, was introduced. QR, which is based on a proof of identifiability of rooted 5-taxon trees in the presence of incomplete lineage sorting, was shown to have good accuracy, improving over other methods for rooting species trees when incomplete lineage sorting was the only cause of gene tree discordance, except when gene tree estimation error was very high. However, the statistical consistency of QR was left as an open question. Here, we present QR-STAR, a polynomial-time variant of QR that has an additional step for determining the rooted shape of each quintet tree. We prove that QR-STAR is statistically consistent under the multispecies coalescent model, and our simulation study shows that QR-STAR matches or improves on the accuracy of QR. QR-STAR is available in open source form at https://github.com/ytabatabaee/Quintet-Rooting. 

   more » « less
2. Phylogenetic Signal of Indels and the Neoavian Radiation

   https://doi.org/10.3390/d11070108  

   Houde, Peter; Braun, Edward L.; Narula, Nitish; Minjares, Uriel; Mirarab, Siavash (July 2019, Diversity)

   The early radiation of Neoaves has been hypothesized to be an intractable “hard polytomy”. We explore the fundamental properties of insertion/deletion alleles (indels), an under-utilized form of genomic data with the potential to help solve this. We scored >5 million indels from >7000 pan-genomic intronic and ultraconserved element (UCE) loci in 48 representatives of all neoavian orders. We found that intronic and UCE indels exhibited less homoplasy than nucleotide (nt) data. Gene trees estimated using indel data were less resolved than those estimated using nt data. Nevertheless, Accurate Species TRee Algorithm (ASTRAL) species trees estimated using indels were generally similar to nt-based ASTRAL trees, albeit with lower support. However, the power of indel gene trees became clear when we combined them with nt gene trees, including a striking result for UCEs. The individual UCE indel and nt ASTRAL trees were incongruent with each other and with the intron ASTRAL trees; however, the combined indel+nt ASTRAL tree was much more congruent with the intronic trees. Finally, combining indel and nt data for both introns and UCEs provided sufficient power to reduce the scope of the polytomy that was previously proposed for several supraordinal lineages of Neoaves. 

   more » « less
3. On Steiner Trees of the regular simplex

   https://doi.org/10.20382/jocg.v16i1a1  

   Fleischmann, Henry; Gamboa_Quintero, Guillermo; Karthik_C, S; Matějka, Josef; Petr, Jakub (January 2025, Journal of computational geometry)

   In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the $$\ell_2$$-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can be introduced as nodes in the solution.  The seminal works of Arora [JACM'98] and Mitchell [SICOMP'99] provide a Polynomial Time Approximation Scheme (PTAS) for solving the Euclidean Steiner Tree problem in fixed dimensions. However, the problem remains poorly understood in higher dimensions (such as when the dimension is logarithmic in the number of terminals) and ruling out a PTAS for the problem in high dimensions is a notoriously long standing open problem (for example, see Trevisan [SICOMP'00]). Moreover, the explicit construction of optimal Steiner trees remains unknown for almost all well-studied high-dimensional point configurations. Furthermore, a vast majority the state-of-the-art structural results on (high-dimensional) Euclidean Steiner trees were established in the 1960s, with no noteworthy update in over half a century. In this paper, we revisit high-dimensional Euclidean Steiner trees, proving new structural results. We also establish a link between the computational hardness of the Euclidean Steiner Tree problem and understanding the optimal Steiner trees of regular simplices (and simplicial complexes), proposing several conjectures and showing that some of them suffice to resolve the status of the inapproximability of the Euclidean Steiner Tree problem. Motivated by this connection, we investigate optimal Steiner trees of regular simplices, proving new structural properties of their optimal Steiner trees, revisiting an old conjecture of Smith [Algorithmica'92] about their optimal topology, and providing the first explicit, general construction of candidate optimal Steiner trees for that topology. 

   more » « less
4. Efficient Projection onto the Perfect Phylogeny Model

   Jia, Bei; Ray, Surjyendu; Safavi, Sam; Bento, Jose (December 2018, Advances in Neural Information Processing Systems 31 (NIPS 2018))

   Several algorithms build on the perfect phylogeny model to infer evolutionary trees. This problem is particularly hard when evolutionary trees are inferred from the fraction of genomes that have mutations in different positions, across different samples. Existing algorithms might do extensive searches over the space of possible trees. At the center of these algorithms is a projection problem that assigns a fitness cost to phylogenetic trees. In order to perform a wide search over the space of the trees, it is critical to solve this projection problem fast. In this paper, we use Moreau's decomposition for proximal operators, and a tree reduction scheme, to develop a new algorithm to compute this projection. Our algorithm terminates with an exact solution in a finite number of steps, and is extremely fast. In particular, it can search over all evolutionary trees with fewer than 11 nodes, a size relevant for several biological problems (more than 2 billion trees) in about 2 hours. 

   more » « less
5. Drought and the interannual variability of stem growth in an aseasonal, everwet forest

   https://doi.org/10.1111/btp.12624  

   Hogan, J. Aaron; McMahon, Sean M.; Buzzard, Vanessa; Michaletz, Sean T.; Enquist, Brian J.; Thompson, Jill; Swenson, Nathan G.; Zimmerman, Jess K. (February 2019, Biotropica)

   Abstract Linking drought to the timing of physiological processes governing tree growth remains one limitation in forecasting climate change effects on tropical trees. Using dendrometers, we measured fine‐scale growth for 96 trees of 25 species from 2013 to 2016 in an everwet forest in Puerto Rico. Rainfall over this time span varied, including an unusual, severe El Niño drought in 2015. We assessed how growing season onset, median day, conclusion, and length varied with absolute growth rate and tree size over time. Stem growth was seasonal, beginning in February, peaking in July, and ending in November. Species growth rates varied between 0 and 8 mm/year and correlated weakly with specific leaf area, leaf phosphorus, and leaf nitrogen, and to a lesser degree with wood specific gravity and plant height. Drought and tree growth were decoupled, and drought lengthened and increased variation in growing season length. During the 2015 drought, many trees terminated growth early but did not necessarily grow less. In the year following drought, trees grew more over a shorter growing season, with many smaller trees showing a post‐drought increase in growth. We attribute the increased growth of smaller trees to release from light limitation as the canopy thinned because of the drought, and less inferred hydraulic stress than larger trees during drought. Soil type accounted for interannual and interspecific differences, with the finest Zarzal clays reducing tree growth. We conclude that drought affects the phenological timing of tree growth and favors the post‐drought growth of smaller, sub‐canopy trees in this everwet forest. Abstract in Spanish is available with online material. 

   more » « less