Name
Abstract | ||
|---|---|---|
Multiple sequence alignment represents a class of powerful bioinformatics tools with many uses in computational biology ranging from discovery of characteristic motifs and conserved regions in protein families to improved prediction of secondary and tertiary structure. Today, with rapidly growing data repositories offering scientists significantly more data with which to make better decisions, it is increasingly important to run these multiple alignment calculations as rapidly as possible. However, while several multiple alignment algorithms have been developed, these algorithms remain computationally expensive taking as long as 2 to 3 days for some queries. In this paper, we propose a new caching technique to improve the performance of multiple sequence alignment algorithms. In particular, we propose a nested two level cache hierarchy that provides caching of pairwise alignment results - a computationally expensive subcomponent of the multiple sequence alignment algorithms. A key contribution of our work is the development of two novel cache replacement policies that closely track the scientist's query patterns over time. We present experimental results that validate the benefits of caching over the repeated computation of the alignments, provide heuristics for determining which alignments would benefit from the caching, and show the effectiveness of the developed cache replacement policies. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/SSDBM.2006.9 | SSDBM |
Keywords | Field | DocType |
multiple alignment calculation,novel cache replacement policy,multiple sequence alignments,multiple sequence alignment,pairwise alignment result,developed cache replacement policy,multiple sequence alignment algorithm,level cache hierarchy,new caching technique,multiple alignment algorithm,computationally expensive subcomponent,computational biology,sequences,data repository,tree data structures,molecular biophysics,data warehouses,proteins,protein family,multiple alignment | Data warehouse,Pairwise comparison,Data mining,Computer science,Cache,Tree (data structure),Information repository,Heuristics,Multiple sequence alignment,Database,Computation | Conference |
ISBN | Citations | PageRank |
0-7695-2590-3 | 0 | 0.34 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xun Tu | 1 | 0 | 0.34 |
| Kajal T. Claypool | 2 | 580 | 64.35 |
| Cindy X. Chen | 3 | 75 | 24.35 |