Automated generation of heuristics for biological sequence comparison Export

@article{citeulike:1341126, abstract = {BACKGROUND: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.RESULTS:The speed and accuracy of this approach compares favourably with existing methods. Examples of its use in the context of genome annotation are given.CONCLUSIONS: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.}, author = {Slater, Guy and Birney, Ewan}, citeulike-article-id = {1341126}, citeulike-linkout-0 = {http://dx.doi.org/10.1186/1471-2105-6-31}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/15713233}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=15713233}, doi = {10.1186/1471-2105-6-31}, issn = {1471-2105}, journal = {BMC Bioinformatics}, keywords = {algorithm, alignment, software}, number = {1}, pages = {31+}, posted-at = {2008-10-08 15:22:58}, priority = {2}, title = {Automated generation of heuristics for biological sequence comparison}, url = {http://dx.doi.org/10.1186/1471-2105-6-31}, volume = {6}, year = {2005} }

TY - JOUR ID - citeulike:1341126 L3 - citeulike-article-id:1341126 N2 - BACKGROUND: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.RESULTS:The speed and accuracy of this approach compares favourably with existing methods. Examples of its use in the context of genome annotation are given.CONCLUSIONS: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. IS - 1 JF - BMC Bioinformatics SN - 1471-2105 TI - Automated generation of heuristics for biological sequence comparison VL - 6 SP - 31 KW - algorithm KW - alignment KW - software AU - Slater, Guy AU - Birney, Ewan PY - 2005/// UR - http://dx.doi.org/10.1186/1471-2105-6-31 ER -