Alignment of BLAST high-scoring segment pairs based on the longest increasing subsequence algorithm.
BACKGROUND
The popular BLAST algorithm is based on a local similarity search strategy, so its high-scoring segment pairs (HSPs) do not have global alignment information. When scientists use BLAST to search for a target protein or DNA sequence in a huge database like the human genome map, the existence of repeated fragments, homologues or pseudogenes in the genome often makes the BLAST result filled with redundant HSPs. Therefore, we need a computational strategy to alleviate this problem.


RESULTS
In the gene discovery group of Celera Genomics, I developed a two-step method, i.e. a BLAST step plus an LIS step, to align thousands of cDNA and protein sequences into the human genome map. The LIS step is based on a mature computational algorithm, Longest Increasing Subsequence (LIS) algorithm. The idea is to use the LIS algorithm to find the longest series of consecutive HSPs in the BLAST output. Such a BLAST+LIS strategy can be used as an independent alignment tool or as a complementary tool for other alignment programs like Sim4 and GenWise. It can also work as a general purpose BLAST result processor in all sorts of BLAST searches. Two examples from Celera were shown in this paper.
Zhang
Hongyu
H
Celera Genomics, 45 West Gude Drive, Rockville, MD 20850, USA. me@hongyu.org
D000465:Algorithms; D020137:Base Pair Mismatch / Q000235:genetics; D020029:Base Pairing / Q000235:genetics*; D001483:Base Sequence; D020869:Gene Expression Profiling / Q000379:methods*; D006801:Humans; D008969:Molecular Sequence Data; D009317:National Library of Medicine (U.S.); D011786:Quality Control; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D014481:United States