GenBlastA: enabling BLAST to identify homologous gene sequences.
BLAST is an extensively used local similarity search tool for identifying homologous sequences. When a gene sequence (either protein sequence or nucleotide sequence) is used as a query to search for homologous sequences in a genome, the search results, represented as a list of high-scoring pairs (HSPs), are fragments of candidate genes rather than full-length candidate genes. Relevant HSPs ("signals"), which represent candidate genes in the target genome sequences, are buried within a report that contains also hundreds to thousands of random HSPs ("noises"). Consequently, BLAST results are often overwhelming and confusing even to experienced users. For effective use of BLAST, a program is needed for extracting relevant HSPs that represent candidate homologous genes from the entire HSP report. To achieve this goal, we have designed a graph-based algorithm, genBlastA, which automatically filters HSPs into well-defined groups, each representing a candidate gene in the target genome. The novelty of genBlastA is an edge length metric that reflects a set of biologically motivated requirements so that each shortest path corresponds to an HSP group representing a homologous gene. We have demonstrated that this novel algorithm is both efficient and accurate for identifying homologous sequences, and that it outperforms existing approaches with similar functionalities.
She
Rong
R
School of Computing Science, Simon Fraser University, Burnaby, British Columbia, V5A 1S6 Canada.
Chu
Jeffrey S-C
JS
Wang
Ke
K
Pei
Jian
J
Chen
Nansheng
N
D000465:Algorithms; D000818:Animals; D017173:Caenorhabditis elegans / Q000235:genetics; D030541:Databases, Genetic; D049751:Genome, Helminth; D023281:Genomics / Q000706:statistics & numerical data; D006801:Humans; D016415:Sequence Alignment / Q000706:statistics & numerical data*; D012689:Sequence Homology, Nucleic Acid; D012984:Software