BIOLOGICAL SEQUENCE ANALYSIS

Biological Sequence Analysis

Biological Sequence Analysis

Answer 1)

A binary search tree is a binary tree of the table elements in which every element x has the lexicographic property that the elements in the left subtree of x are before the key of x in the natural order and the elements in the right subtree of x are after the key of x in the natural order. This property of the tree makes it easy to search for an element z: compare z with the key of the root element; if the keys are equal, the search ends successfully, and if they are not, search the left or right subtree according to whether z is less than or greater than the key of the root element, respectively.

The application of binary search trees to static tables is concerned entirely with choosing the tree that minimizes search time; we assume that the table is constructed once and that its contents never change, or change so infrequently that the entire table will be reconstructed to make the change. If we want to minimize the worst-case search time, we simply use the tree corresponding to binary search, and we do not need an explicit tree at all. The more difficult problem is to minimize the average search time, given some frequency distribution of how the search will end. If the table consists of elements x1 < x2 < … < xn, then the search can end successfully at any of the x1 (internal nodes) and unsuccessfully in any of the n + 1 intervals (leaves) specified by the xi and the endpoints. If we are given the relative frequencies with which the search ends in these 2n + 1 ways, we can use dynamic programming to determine the optimal shape of the tree that minimizes the average search time (Chung, 2007).

The dynamic programming algorithm can be implemented in quadratic time, but it may not be worth spending so much time to construct the optimal tree if we have only inaccurate values for the relative frequencies. Instead, we should use a heuristic (q.v.) to construct a “near-optimal tree” rapidly. The balancing heuristic chooses the root so as to equalize (as much as possible) the frequencies with which a search will end in the left and right subtrees. Binary search trees can be used for dynamic tables— tables whose contents change because of insertions and deletions. There is a conflict between efficient search algorithms and efficient modification: fast search requires a rigid structure, while fast modification needs a flexible structure; balanced trees provide a compromise between the two requirements.

Answer 2)

Most alignment programs make comparisons between pairs of bases or amino acids by looking up a value in a scoring matrix. The matrix contains a score for the match quality of every possible pair of residues. The simplest way to score an alignment is to count the number of identical residues that are aligned. When the sequences to be aligned are closely related, this ...