Abstract
Comparing multiple genome sequences is an important method to discover new biological insights. If a group of genes remain physically close to each other in multiple genomes, often called a conserved gene cluster, then the genes may be either historically or functionally related. A gene team is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. In this dissertation, new efficient algorithms are presented for the problem of constructing a gene team tree of two chromosomes. For this problem, Zhang and Leong had an O(n lg^2 n)-time algorithm, where n is the number of genes. In this dissertation, two improved algorithms are presented, which require, respectively, O(n lg n lglg n) and O(n lg n α(n)) time, where α(n) is the inverse of Ackermann's function. Similar to Zhang and Leong's gene-team-tree algorithm, the presented algorithms can be extended to k chromosomes with the time complexities increased only by a factor of k, where k > 2 is an integer. In practice, the distance between two genes is integer. In addition to the two improved algorithms, assuming that the positions of genes are integers, this dissertation presents an O(n lg n + z)-time algorithm, where z is the maximum distance between any two adjacent genes. For real-world applications, z is usually smaller than n and thus the third algorithm is more efficient than the other two algorithms. Similarly, it can be extended to k chromosomes. The extended algorithm requires O(kn lg n + z) time.