Design and Analysis of Algorithms for Finding the Maximum Quasi-Biclique, Perfect Duplication History and Identification of Linked Regions

Description

In this project, the researchers will design algorithms for the three important problems in computational biology: (1) finding the maximum quasi-biclique, (2) the perfect duplication history problem, and (3) identification of linked regions.The problem of finding the maximum quasi-biclique is a core mathematical problem in modelling protein-protein interaction groups. The perfect duplication history problem is a new model for tandem repeated regions proposed in this project. Recently, the investigators have observed that lots of real datasets fit the perfect duplication history model. Biologists believe that tandem repeated regions are closely related to some genetic diseases in human beings. The fundamental problem in linkage analysis is to identify regions whose allele is shared by all or most affected members in a family but by none or few unaffected family members. Recent studies show that high-density SNP genotype data, such as those from microarrays, can be used for large-scale and cost-effective linkage analysis. Here the researchers propose to use a deterministic approach for finding the linked regions. The project will emphasize algorithmic issues for all the proposed problems.