The origin of cilia and eukaryotic cell are two fundamental problems listed among the twelve fundamental problems for bioinformatics. The readers interested in learning about what the issues are may take a look at the following 2009 paper of Temple Smith (of Smith-Waterman fame).
The Cilium, the Nucleus and the Mitochondrion are three important organelles whose evolutionary histories are intimately related to the evolution and origin of the eukaryotic cell. The cilium is involved in motility and sensory transduction. The cilium is only found in the eukaryotic cells. Here we show that eight gene duplications prior to the last common ancestor of all extant eukaryotes account for the expansion of the Heavy Chain Dynein family of motor proteins and the evolution of the complexity of the cilium. The ambiguities in the branching of the phylogenetic tree of the HC-Dyneins were resolved by creating well-defined subtrees and using them to create the full tree. Due to the intimate relationship between the nucleus, the division center, mitosis and the basal body/centriole, the evolution of the cilium can now be related to the evolution of mitosis. In addition, the analysis of the cilium rules out its endosymbiotic origin from a phagocytosis of a bacterium.
Temple Smith is also busy solving the most difficult problem in computational biology, which involves figuring out how the translational machinery and genetic code came into place.