Design and Analysis of Algorithms for Finding the Original Configurations from Many Noisy Copies

Description

In computational biology, many problems being faced require finding the truth from several noisy copies. In this project, the researchers will study some interesting problems that find the original configurations from many noisy copies. The problems that will be studied include shotgun protein sequencing from mass spectra, probabilistic analysis for local multiple sequence alignment and motif identification, and translocation distance. The shotgun protein sequencing approach uses several enzymes to cut the protein string so that obtained peptides have overlaps, and the researchers will use the overlaps to improve the quality of the reconstructed peptides and possibly reconstruct the whole string. They will give some probabilistic analysis for local multiple sequence alignment and motif detection problems and show that when the number of strings increases, the “true” motif/alignment has the optimal objective function score based on their probabilistic models. They will also design algorithms for unsigned translocation distance with a better ratio. The project will emphasize algorithmic issues for all the proposed problems.