Algorithms for Scaffold Synthesis and Pedigree Comparison

Description

In this project, we will design algorithms for two important problems in computational biology, scaffold synthesis and comparison of pedigrees.Genome comparison is an important area in computational biology. It holds great promise for yielding insights into various aspects of the evolution of species and important strains of the same species. With the development of genome sequencing technology, more and more organisms have been sequenced. An interesting phenomenon is that many released genomes are incomplete and there are an increasing number of genomes being published in contig form. In biological studies of bacterial strains, several different strains of the same species were sequenced and published in contig forms. In this project, we will study the scaffold synthesis problem and design efficient algorithms.The reconstruction of ancestral relationships among genera, species and populations is a core task in evolutionary biology. At the species level, phylogenetic methods have been traditionally used, while for populations, pedigrees have been more commonly employed. Reconstruction of pedigree is required in practice due to legal or medical reasons. Pedigrees are very important to geneticists for inferring haplotype segments, recombination, and allele sharing status with which disease loci can be identified. In this project, we will study various measures for the pedigree comparison problem and design efficient algorithms to compute those measures.