Finding conserved patterns in biological sequences, networks and genomes

摘要

Biological patterns are widely used for identifying biologically interesting regionswithin macromolecules, classifying biological objects, predicting functions and studyingevolution. Good pattern finding algorithms will help biologists to formulate andvalidate hypotheses in an attempt to obtain important insights into the complexmechanisms of living things.In this dissertation, we aim to improve and develop algorithms for five biologicalpattern finding problems. For the multiple sequence alignment problem, we proposean alternative formulation in which a final alignment is obtained by preserving pairwisealignments specified by edges of a given tree. In contrast with traditional NPhardformulations, our preserving alignment formulation can be solved in polynomialtime without using a heuristic, while having very good accuracy.For the path matching problem, we take advantage of the linearity of the querypath to reduce the problem to finding a longest weighted path in a directed acyclicgraph. We can find k paths with top scores in a network from the query path inpolynomial time. As many biological pathways are not linear, our graph matchingapproach allows a non-linear graph query to be given. Our graph matching formulationovercomes the common weakness of previous approaches that there is noguarantee on the quality of the results.For the gene cluster finding problem, we investigate a formulation based on constraining the overall size of a cluster and develop statistical significance estimates thatallow direct comparisons of clusters of different sizes. We explore both a restrictedversion which requires that orthologous genes are strictly ordered within each cluster,and the unrestricted problem that allows paralogous genes within a genome and clustersthat may not appear in every genome. We solve the first problem in polynomialtime and develop practical exact algorithms for the second one.In the gene cluster querying problem, based on a querying strategy, we proposean efficient approach for investigating clustering of related genes across multiplegenomes for a given gene cluster. By analyzing gene clustering in 400 bacterialgenomes, we show that our algorithm is efficient enough to study gene clusters acrosshundreds of genomes.