Loading...
Please wait, while we are loading the content...
Similar Documents
Divide-and-conquer frontier search applied to optimal sequence alignment (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Korf, Richard E. |
| Description | In National Conference on Artificial Intelligence (AAAI We present a new algorithm that reduces the space complexity of heuristic search. It is most e ective for problem spaces that grow polynomially with problem size, but contain large numbers of short cycles. For example, the problem of nding an optimal global alignment ofseveral DNA or amino-acid sequences can be solved by nding a lowest-cost corner-to-corner path in a d-dimensional grid. A previous algorithm, called divide-and-conquer bidirectional search (Korf 1999), saves memory by storing only the Open lists and not the Closed lists. We show that this idea can be applied in a unidirectional search aswell. This extends the technique to problems where bidirectional search is not applicable, and is more e cient in both time and space than the bidirectional version. If n is the length of the strings, and d is the number of strings, this algorithm can reduce the memory requirement from O(n d) to O(n d;1). While our current implementation of DCFS is somewhat slower than existing dynamic programming approaches for optimal alignment of multiple gene sequences, DCFS is a more general algorithm 1 |
| File Format | |
| Language | English |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Optimal Global Alignment Ofseveral Dna Heuristic Search Dynamic Programming Approach Short Cycle Problem Size New Algorithm General Algorithm Lowest-cost Corner-to-corner Path Closed List Space Complexity Multiple Gene Sequence Open List Divide-and-conquer Frontier Search Divide-and-conquer Bidirectional Search Optimal Sequence Alignment Optimal Alignment Unidirectional Search Aswell Amino-acid Sequence Large Number Bidirectional Search Bidirectional Version Previous Algorithm Problem Space Memory Requirement D-dimensional Grid Current Implementation |
| Content Type | Text |
| Resource Type | Article |
