Algorithms for Finding Center Strings from a Set of Input Strings
Project: Research
Researcher(s)
Description
Computational biology is a rapidly developing area that plays a crucial role in biological research. Our project aims at the design and analysis of algorithms for two important problems in computational biology, the haplotype assembly problem and mutation region detection problem. Single nucleotide polymorphisms (SNPs) are the most frequent form of human genetic variation. The SNP sequence information from each of the two strands of a given chromosome in a diploid genome is a haplotype. Haplotype information has been attracting great attention in recent years because of its importance in various applications such as the mapping of complex disease genes, linked region detection, inferring population histories and designing drugs. Traditional approaches for obtaining haplotypes involve collecting genotype information from a set of individuals. With the development of high-throughput sequencing technologies, an alternative strategy to obtain the haplotype for an individual is to combine sequence fragments. This is referred to as the haplotype assembly problem. In this project, we will study several variations/models for the haplotype assembly problem and design efficient algorithms. Mutation region detection methods have facilitated the identification of several hundreds of human genes that can harbor mutations that by themselves lead to a disease phenotype. The fundamental problem is identifying regions whose allele is shared by all or most of the diseased individuals but by none or few normal individuals. All the previous methods for mutation region detection are for families with pedigrees. Little has been done for the important case that the set of input individuals are closely related and the pedigree is not known. We will design fixed-parameter algorithms and approximation algorithms for the shared centre problem arising in mutation region detection study.Detail(s)
Project number | 7002728 |
---|---|
Grant type | SRG |
Status | Finished |
Effective start/end date | 1/05/12 → 17/11/15 |