An adaptive grid implementation of DNA sequence alignment

被引：16

作者：

Chen, CX ^{[1
]}

Schmidt, B ^{[1
]}

机构：

[1] Nanyang Technol Univ, Sch Comp Engn, Singapore 2263, Singapore

来源：

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE | 2005年 / 21卷 / 07期

关键词：

sequence alignment; grid computing; MPI; dynamic programming;

D O I：

10.1016/j.future.2005.03.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we have described a dynamic programming algorithm to compute k non-intersecting near-optimal alignments in linear space. In order to reduce its runtime significantly, we are using a hierarchical grid system as the computing platform. Static and dynamic load balancing approaches are investigated in order to achieve efficiently mapping onto this type of architecture, which has characteristics such as: (1) the resources in the grid systems have different computational power; (2) the resources usually are connected by networks with widely varying performance characteristics. At last, a new dynamic load balancing approach named scheduler-worker parallel paradigm is proposed and evaluated. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：988 / 1003

页数：16

共 27 条

[11] An architecture of Stampi: MPI library on a cluster of parallel computers [J].

Imamura, T ;

Tsujita, Y ;

Koide, H ;

Takemiya, H .

RECENT ADVANCES IN PARALLEL VIRTUAL MACHINE AND MESSAGE PASSING INTERFACE, PROCEEDINGS, 2000, 1908 :200-207

[12]

Kaishima T, 2002, LECT NOTES COMPUT SC, V2550, P98

[13]

Kielmann T., 1999, PPoPP '99 Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, P131

[14]

LIU WG, 2003, CLUSTER 2003

[15]

MARTINS WS, 2001, P 13 S COMP ARCH HIG

[16]

MULLER M, 2003, CCGRID 03

[17] OPTIMAL ALIGNMENTS IN LINEAR-SPACE [J].

MYERS, EW ;

MILLER, W .

COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1988, 4 (01) :11-17

[18] COMPARISON OF METHODS FOR SEARCHING PROTEIN-SEQUENCE DATABASES [J].

PEARSON, WR .

PROTEIN SCIENCE, 1995, 4 (06) :1145-1160

[19] Sensitivity of parallel applications to large differences in bandwidth and latency in two-layer interconnects [J].

Plaat, A ;

Bal, HE ;

Hofman, RFH .

FIFTH INTERNATIONAL SYMPOSIUM ON HIGH-PERFORMANCE COMPUTER ARCHITECTURE, PROCEEDINGS, 1999, :244-253

[20] A hybrid architecture for bioinformatics [J].

Schmidt, B ;

Schröder, H ;

Schimmler, M .

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2002, 18 (06) :855-862

← 1 2 3 →