Phylogenetic inference presents enormous computational and mathematical challenges, but these are particularly exacerbated when dealing with very large datasets (containing thousands of sequences) or when sequences evolve under complex evolutionary processes (ranging from simple "indel" models, to horizontal gene transfer, to genome rearrangement events). In this talk, I will describe some of the recent progress on evolutionary history reconstructing under complex evolutionary processes, focusing in particular on multiple sequence alignment and its implications for large-scale phylogenetics. Related Link: http://www.phylo.org - CIPRES project webpage.