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

Description

In computational biology, many problems are faced that require finding the truth from several noisy copies. For sequence alignment, “pair-wise alignments whisper while multiple alignments shout out loudly”. In this project, the researchers intend to study some interesting problems that find the original configurations from many noisy copies. The problems include the following:shotgun protein sequencing from mass spectra—this 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;local multiple sequence alignment and motif identification problems—the researchers will give some probabilistic analysis for local multiple sequence alignment and motif detection problems and will show that when the number of strings increases, the “true” motif/alignment has the optimal objective function score based on their probabilistic models; andtranslocation distance—the researchers will design algorithms for unsigned translocation distance with better ratio.The project will emphasize algorithmic issues for all of the proposed problems.