In database searches for sequence similarity, matches to a distinct sequence region (e.g. protein domain) are frequently obscured by numerous matches to another region of the same sequence.In order to cope with this problem, algorithms are developed to discard redundant matches.One model for this problem begins with a list of intervals, each with an associated score; each interval gives the range of positions in the query sequence that align to a database sequence, and the score is that of the alignment.If interval I is contained in interval J, and I's score is less than J's, then I is said to be dominated by J.The problem is then to identify each interval that is dominated by at least K other intervals, where K is a given level of "tolerable redundancy."An algorithm is developed to solve the problem in O(N log N) time and O(N*) space, where N is the number of intervals and N' is a precisely defined value that never exceeds N and is frequently much smaller.This criterion for discarding database hits has been implemented in the Blast program, as illustrated herein with examples.Several variations and extensions of this approach are also described.

MOTIVATION: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments. RESULTS: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment's length. Practical applications to alignments of genomic DNA sequences are described.

Given a strong match be%een regions of txvo sequences, horn far can the match be meaningfully extended if gaps are all04 in the resdtinrc aknment?The aim is to aviod sear&ix bwond the point th\t asuseful extension of the a&mm& is l&ly to be found.Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem.Given two sequences and a fixed X > 0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X.Our results indicate that computing an optimal alignment under this constraint is very expensive.However, less rigorous conditions on the alignment can be guaranked by quite eiiicient algorithms.One of these variants has been implemented in a new release of the Blast suite of database search programs.a b C Figure 1: Graph model of a simple alignment problem.Dark edges (corresponding to aligning identical letters) score 1, and all other edges score -1.

A progressive alignment algorithm produces a multi-alignment of a set of sequences by repeatedly aligning pairs of sequences and/or previously generated alignments. We describe a method for guaranteeing that the alignment generated by a progressive alignment strategy satisfies a user-specified collection of constraints about where certain sequence positions should appear relative to others. Given a collection of C constraints over K sequences whose total length is N , our algorithm takes O(K(N 2 +KC)) time. An alignment of the fi-like globin gene clusters of several mammals illustrates the practicality of the method. Key words: Multiplesequence alignment, constrained alignment, dynamic programming 1 Introduction It is straightforward to extend the dynamic programming alignment algorithm (Needleman and Wunsch 1970) to the simultaneous alignment of K ? 2 sequences. However, the O(2 K N K ) execution time for sequences of length N makes it impractical to align more than three seque...

We develop several algorithms for the problem of aligning a DNA sequence with a protein sequence.Our methods account for frameshift errors, but not for introns in the DNA sequence.Thus, they are particularly appropriate for comparing a cDNA sequence that contains sequencing errors with an amino acid sequence or a protein sequence database.We describe techniques for efficient implementation, verify sufficient conditions for equivalenceof several definitions of alignment, and discuss experience with these ideas in a new release of the fasta suite of database-searching programs.