The textbook (Computational Phylogenetics: An Introduction to Designing Methods for Phylogeny Estimation) has several suggestions for projects, many of which would be good for this course. You may also have your own ideas for a project! The suggestions below are just to get you started with thinking about what you might do. (Note, however, that some projects--especially those that evaluate and explore Bayesian methods, may be too computationally intensive to do as a course project, and would be better as a post-581 project.)

Specific projects of interest to me (TW)

1. Projects related to TIPP (https://doi.org/10.1093/bioinformatics/btu721)
   • Improve phylogenetic placement on very large trees (20K sequences or more)-- compare to pplacer (https://doi.org/10.1186/1471-2105-11-538) and APPLES (https://doi.org/10.1093/sysbio/syz063)
   • Modify TIPP so that it places into a gene tree and then inherits the taxonomic information from the leaf labels.
   • Compare HIPPI (https://doi.org/10.1186/s12864-016-3097-0) to BLAST for gene assignment on nucleotide sequences
2. Projects related to tree estimation
   • Test GTM (https://doi.org/10.1186/s12864-020-6605-1) and TreeMerge (https://doi.org/10.1093/bioinformatics/btz344), two Disjoint Tree Merger methods, under conditions with different model tree topologies (balanced vs. caterpillar)
   • Develop a new quartet amalgamation method and compare to Quartets Max Cut (DOI: 10.1109/TCBB.2008.133)
   • Evaluate methods for tree construction in the presence of rogue taxa (that are nevertheless homologs)
   • Compare A-Pro (https://doi.org/10.1093/molbev/msaa139) to FastMulRFS (doi:10.1093/bioinformatics/btaa444) on datasets with multi-copy genes
3. Projects related to ensembles of HMMs
   • Develop a new method based on ensembles of profile HMMs to identify non-homologs
   • Develop a rigorous way of designing ensembles of profile HMMs (think cross-validation)
   • Extend design or use of ensemble of HMMs in some interesting way (e.g., use some other generative model, or define a mixture model)
4. Projects related to multiple sequence alignment (MSA)
   • Test existing MSA methods on datasets with sequence length heterogeneity where some sequences are very long
   • Develop and test methods for merging two disjoint alignments of different lengths
   • Test Prank in comparison to MAFFT as evolutionary diameter and deviation from a clock increase, when given a guide tree
   • Evaluate Prank within PASTA, given the true tree
   • Compare Regressive (https://doi.org/10.1038/s41587-019-0333-6) to PASTA
   • Evaluate when iteration is needed in PASTA for MSA or tree accuracy
5. Parallel algorithms projects:
   • Parallelize UPP (multiple sequence alignment, by Nam-phuong Nguyen et al.)
   • Parallelize GTM (Guide Tree Merger, by Vlad Smirnov and me)
   • Parallelize Balanced Minimum Evolution within FastME

Other targeted interest projects are given in boldface below

Projects related to multiple sequence alignment

1. Modify the sequence evolution simulator Indelible (Fletcher and Yang) so that it allows the root sequence to be specified. The code is open source and written in C++.
2. Compare methods that can align two alignments, and evaluate for accuracy on simulated datasets. Examples of such methods: Opal, Muscle, and Prime.
3. Many alignment methods have been evaluated in terms of standard alignment criteria (SPFN, SPFN, column score) and some have been evaluated in terms of the impact on tree topology accuracy. However, very few have been evaluated in terms of impact on estimating numeric parameters such as the GTR substitution matrix or branch lengths. Perform such an evaluation.
4. Design a method that can find outliers in a set of sequences (i.e., can find the sequences that are not homologous to the remaining sequences), under the assumption that nearly all the input set are homologous to each other.
5. Test POY using gap penalties that are not affine gap penalties for accuracy.
6. Examine ways of computing a consensus alignment on the output from PASTA, and evaluate for accuracy in comparison to the single alignment returned by PASTA. For example, compute the posterior decoding of a random sample of the alignments PASTA computes (after removing the first few alignments). To compute the posterior decoding, you can install BAli-Phy (Redelings and Suchard), using the directions on the website: http://balip-phy.org/README.html#installation. Once the software is installed, there is a folder of executable files called "bin", and within that folder there is a folder called "alignment-max".
7. Examine ways to annotate the sites in a multiple sequence alignment for reliability, based on examining a set of alternate alignments obtained by running a basic alignment method using different strategies (e.g., different parameter settings).
8. Find codes for computing a point estimate of an alignment given an arbitrary set of multiple sequence alignments (e.g., the posterior decoding algorithm in BAli-Phy, but also look at T-Coffee), and compare them for accuracy and/or scalability.
9. Explore BAli-Phy to see if you can improve it. For example, determine if you can use it to score a given alignment/tree pair, to find a tree given a fixed alignment, or to find the best alignment on a fixed tree. Or see if you can improve it by giving it a good starting alignment/tree pair. Or see if it is missing any important substitution models, and if so modify it to enable them.
10. It is well known that over-alignment (where the computed alignment is shorter than the true alignment) can lead to false discovery of positive selection (i.e., the conclusion that there is positive selection even when there is in fact no such positive selection). What are the other impacts of over-alignment? For example, does over-alignment result in the expansion of branch lengths? It is known that many alignment methods (e.g., MAFFT and Clustal-Omega) tend to over-align, so understanding the impact of over-alignment is important.
11. Less is known about the impact of under-alignment, however, and yet some methods (notably PASTA, Prank, and PAGAN) tend to under-align. Evaluate methods that under-align to determine the impact of under-alignment (e.g., on branch lengths, on the GTR matrix, on detecting selection, on tree topology estimation, etc.)
12. PASTA is a method that iterates between tree estimation and alignment estimation, and has very good accuracy in tree topology estimation on very large datasets. However, PASTA often under-aligns (and so produces alignments that are longer than they should be. Try to modify the output of PASTA so that you reduce the under-alignment tendency, perhaps by considering the set of alignment/tree pairs it produces.
13. In "Benchmarking statistical multiple sequence alignment" (bioRxiv doi: https://doi.org/10.1101/304659), my students and I showed a strange trend in which BAli-Phy did very well on simulated amino acid datasets but not very well on biological amino acid datasets. Try to do this evaluation on nucleotide datasets.
14. Compare standard maximum likelihood methods (that treat gaps as missing data) to BAli-Phy (which treats gaps as insertions and deletions, under a statistical model) on simulated data, given an alignment (e.g., either the true alignment or an estimated alignment).
15. Evaluate the impact of violating the strict molecular clock on either multiple sequence alignment or phylogenetic tree estimation, especially when using statistical methods (such as BAli-Phy, Prank, etc.).

Projects related to supertree estimation or phylogenomic species tree estimation

1. Develop a good method for weighted quartet tree amalgamation. Compare to Weighted Quartets MaxCut by Avni et al. (2014), DOI: 10.1093/sysbio/syu087.
2. Evaluate Weighted Quartets MaxCut (Avni et al. 2014) as a supertree method on the SMIDgen datasets (Swenson et al.).
3. Implement a parallel version of some good supertree method, such as FastRFS (Vachaspati and Warnow), Quartets MaxCut (Snir and Rao), etc.
4. Quartet-based supertree methods have computational limitations in that they depend on computing all quartet trees. Evaluate variants that only require computing a subset of the quartet trees.
5. Evaluate the impact of multiple sequence alignment error on SVDquartets (Chifman and Kubatko, as implemented in PAUP*).

Projects related to maximum likelihood gene tree estimation

1. Develop parallel implementation of FastTree-2.
2. Evaluate the impact of the starting tree on FastTree-2.
3. ML methods have been explored in terms of the impact of the tree topology or the ML score, and in general RAxML has been found to be better than other methods for ML score but only rarely better than FastTree-2 in terms of tree topology. Try to characterize the conditions in which RAxML is generally more accurate than FastTree-2 (or other ML methods) for tree topology.
4. Test some leading maximum likelihood methods on large datasets (be careful - this will require a lot of computing time).
5. Test some leading maximum likelihood method (e.g., RAxML) on simulated datasets that evolved with heterotachy, and compare to maximum parsimony and distance-based methods. Note: I don't know if any simulator exists that evolves sequences with heterotachy; if not, then another project is to create such a simulator.
6. Modify some maximum likelihood method to take support values per site into account.
7. Test divide-and-conquer strategies using a Disjoint Tree Merger method (e.g., either GTM or TreeMerge) in the presence of heterotachy.
8. Develop a new DTM method, and test it.
9. Evaluate the impact of violating the strict molecular clock on on phylogenetic tree estimation, especially when using statistical methods such as BAli-Phy.
10. Evaluate the impact of tree shape (e.g., the Aldous beta-splitting model) on tree estimation.

Other

1. Develop a method that can compute a tree from an incomplete dissimilarity matrix (i.e., matrices where some of the entries do not have values). Compare to the "NJ*" methods from Criscuolo and Gascuel (2008), https://doi.org/10.1186/1471-2105-9-166, on some simulated datasets.
2. Find an application area (other than biological phylogenetics) where tree estimation (especially of large datasets) is important and not necessarily solved well, and where accuracy can be measured. Try to develop a new approach to tree estimation, and compare to the current best methods.
3. Explore the "ensemble of profile HMMs" approach with some other generative model, or on some other problem. Or vary how the ensemble is built or used. For example, consider combinations of the profile HMMs within the model.
4. Develop a new method for phylogenetic placement, and compare to leading methods for this problem.
5. Develop a method that performs taxon identification of sequences that takes the following as input: a taxonomy T and a tree T' in which all but one of the leaves is assigned a taxonomic label using T. Test your method where T' is produced by adding a single short sequence (i.e., read) into an estimated maximum likelihood tree on full length sequences for a single gene. Thus, your method will rely on a phylogenetic placement method.
6. Develop a divide-and-conquer approach to phylogenetic network estimation, and test it.
7. Test divide-and-conquer DTM methods for use with genome rearrangement phylogeny estimation methods.
8. Find some published dataset and re-analyze it using the new methods for phylogeny estimation (either gene trees or species trees).

People who can help

• Vladimir Smirnov, PhD student in the Warnow lab. Contact Vlad at smirnov3@illinois.edu.