Slater Guy St C, Birney Ewan
The Ensembl Group, EMBL-European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge, CB10 1SD, UK.
BMC Bioinformatics. 2005 Feb 15;6:31. doi: 10.1186/1471-2105-6-31.
Exhaustive methods of sequence alignment are accurate but slow, whereas heuristic approaches run quickly, but their complexity makes them more difficult to implement. We introduce bounded sparse dynamic programming (BSDP) to allow rapid approximation to exhaustive alignment. This is used within a framework whereby the alignment algorithms are described in terms of their underlying model, to allow automated development of efficient heuristic implementations which may be applied to a general set of sequence comparison problems.
The speed and accuracy of this approach compares favourably with existing methods. Examples of its use in the context of genome annotation are given.
This system allows rapid implementation of heuristics approximating to many complex alignment models, and has been incorporated into the freely available sequence alignment program, exonerate.
详尽的序列比对方法准确但速度慢，而启发式方法运行速度快，但其复杂性使其更难实现。我们引入有界稀疏动态规划（BSDP）以实现对详尽比对的快速近似。这在一个框架内使用，在该框架中，比对算法根据其基础模型进行描述，以允许自动开发高效的启发式实现，这些实现可应用于一般的序列比较问题集。
该方法的速度和准确性与现有方法相比具有优势。给出了其在基因组注释背景下的使用示例。
该系统允许快速实现近似许多复杂比对模型的启发式方法，并且已被纳入免费的序列比对程序exonerate中。
