DocumentCode
2358512
Title
Sweep A: space-efficient heuristic search in partially ordered graphs
Author
Zhou, Rong ; Hansen, Eric A.
Author_Institution
Dept. of Comput. Sci. & Eng., Mississippi State Univ., USA
fYear
2003
fDate
3-5 Nov. 2003
Firstpage
427
Lastpage
434
Abstract
We describe a novel heuristic search algorithm, called Sweep A*, that exploits the regular structure of partially ordered graphs to substantially reduce the memory requirements of search. We show that it outperforms previous search algorithms in optimally aligning multiple protein or DNA sequences, an important problem in bioinformatics. Sweep A* also promises to be effective for other search problems with similar structure.
Keywords
DNA; biology computing; heuristic programming; proteins; search problems; DNA sequence; Sweep A; bioinformatics; deoxyribonucleic acid; heuristic search algorithm; memory requirement; multiple protein aligning; partially ordered graph; space-efficient heuristic search; Bioinformatics; Computer science; DNA; Dynamic programming; Heuristic algorithms; History; Proteins; Search problems; Sequences; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Tools with Artificial Intelligence, 2003. Proceedings. 15th IEEE International Conference on
ISSN
1082-3409
Print_ISBN
0-7695-2038-3
Type
conf
DOI
10.1109/TAI.2003.1250221
Filename
1250221
Link To Document