Bioinformatics is an emerging multi-disciplinary field. In this research, we study two problems originating from biological applications using signal processing and statistical patter recognition techniques: (1) the genomic sequence alignment problem, and (2) the data integrity problem on Single Nucleotide Polymorphisms (SNP) data sets.

First, we introduced a gap sequence matching technique, which facilitates the match of genomic sequences. We studied the behavior of these gap sequences and proposed two methods, histogram-aided alignment (HAA) and matched filter alignment (MFA), to perform the alignment for pairwise and multiple genomic sequences. The main contribution here is that, even with partial knowledge of a genomic sequence (namely, the gap structure), we are able to accurately predict the remaining portions of the sequence using arguments from information theory. We proposed a fast gap sequence alignment system with suffix array implementation (GSA-SA). This system outperforms the current BLAST system (build 2.2.13) in terms of time and accuracy. Since BLAST is the most widely used system for sequence alignment, we expect GSA-SA to facilitate the sequence alignment technique in the near future.

Next, the problem of haplotype block partitioning and missing SNP inference was studied. We proposed to measure the haplotype diversity inside a block using the entropy. Based on this measure, we developed a new algorithm, called IPI (iterative partitioning-inference). The IPI algorithm consists of two steps. In the first step, a dynamic programming algorithm is adopted to partition haplotype data into blocks to minimize the total block entropy. In the second step, an EM-like algorithm is used to infer missing SNPs in each haplotype block to minimize the local block diversity. The IPI algorithm iterates these two steps until the total block entropy is minimized. It was shown by experimental results that the global IPI approach significantly improves the accuracy of the inference. Then, we considered the block-free framework that can accommodate larger data sets for missing SNP inference, without partitioning the haplotype block. The block-free inference system can be extended to haplotype inference and missing genotype inference. Our developed systems can infer all kinds of uncertain data from available data sets.