Search space reduction technique for distributed multiple sequence alignment

Manal Helal; Lenore Mullin; John Potter; Vitali Sintchenko

doi:10.1109/NPC.2009.43

Search space reduction technique for distributed multiple sequence alignment

Manal Helal, Lenore Mullin, John Potter, Vitali Sintchenko

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

To take advantage of the various High Performance Computer (HPC) architectures for multi-threaded and distributed computing, this paper parallelizes the dynamic programming algorithm for Multiple Sequence Alignment (MSA). A novel definition of a hyper-diagonal through a tensor space is used to reduce the search space. Experiments demonstrate that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are often better than other heuristic methods and are capable of aligning more divergent sequences.

Original language	English
Title of host publication	NPC 2009 - 6th International Conference on Network and Parallel Computing
Pages	219-226
Number of pages	8
DOIs	https://doi.org/10.1109/NPC.2009.43
Publication status	Published - 2009
Event	NPC 2009 - 6th International Conference on Network and Parallel Computing - Gold Coast, QLD, Australia Duration: 19 Oct 2009 → 21 Oct 2009

Publication series

Name	NPC 2009 - 6th International Conference on Network and Parallel Computing

Conference

Conference	NPC 2009 - 6th International Conference on Network and Parallel Computing
Country/Territory	Australia
City	Gold Coast, QLD
Period	19/10/09 → 21/10/09

Access to Document

10.1109/NPC.2009.43

Cite this

@inproceedings{fdf40cc1fdb1465aa0c456cd5230e57c,

title = "Search space reduction technique for distributed multiple sequence alignment",

abstract = "To take advantage of the various High Performance Computer (HPC) architectures for multi-threaded and distributed computing, this paper parallelizes the dynamic programming algorithm for Multiple Sequence Alignment (MSA). A novel definition of a hyper-diagonal through a tensor space is used to reduce the search space. Experiments demonstrate that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are often better than other heuristic methods and are capable of aligning more divergent sequences.",

author = "Manal Helal and Lenore Mullin and John Potter and Vitali Sintchenko",

year = "2009",

doi = "10.1109/NPC.2009.43",

language = "English",

isbn = "9780769538372",

series = "NPC 2009 - 6th International Conference on Network and Parallel Computing",

pages = "219--226",

booktitle = "NPC 2009 - 6th International Conference on Network and Parallel Computing",

note = "NPC 2009 - 6th International Conference on Network and Parallel Computing ; Conference date: 19-10-2009 Through 21-10-2009",

}

Helal, M, Mullin, L, Potter, J & Sintchenko, V 2009, Search space reduction technique for distributed multiple sequence alignment. in NPC 2009 - 6th International Conference on Network and Parallel Computing., 5328501, NPC 2009 - 6th International Conference on Network and Parallel Computing, pp. 219-226, NPC 2009 - 6th International Conference on Network and Parallel Computing, Gold Coast, QLD, Australia, 19/10/09. https://doi.org/10.1109/NPC.2009.43

Search space reduction technique for distributed multiple sequence alignment. / Helal, Manal; Mullin, Lenore; Potter, John et al.
NPC 2009 - 6th International Conference on Network and Parallel Computing. 2009. p. 219-226 5328501 (NPC 2009 - 6th International Conference on Network and Parallel Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Search space reduction technique for distributed multiple sequence alignment

AU - Helal, Manal

AU - Mullin, Lenore

AU - Potter, John

AU - Sintchenko, Vitali

PY - 2009

Y1 - 2009

N2 - To take advantage of the various High Performance Computer (HPC) architectures for multi-threaded and distributed computing, this paper parallelizes the dynamic programming algorithm for Multiple Sequence Alignment (MSA). A novel definition of a hyper-diagonal through a tensor space is used to reduce the search space. Experiments demonstrate that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are often better than other heuristic methods and are capable of aligning more divergent sequences.

AB - To take advantage of the various High Performance Computer (HPC) architectures for multi-threaded and distributed computing, this paper parallelizes the dynamic programming algorithm for Multiple Sequence Alignment (MSA). A novel definition of a hyper-diagonal through a tensor space is used to reduce the search space. Experiments demonstrate that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are often better than other heuristic methods and are capable of aligning more divergent sequences.

UR - http://www.scopus.com/inward/record.url?scp=73449094885&partnerID=8YFLogxK

U2 - 10.1109/NPC.2009.43

DO - 10.1109/NPC.2009.43

M3 - Conference contribution

AN - SCOPUS:73449094885

SN - 9780769538372

T3 - NPC 2009 - 6th International Conference on Network and Parallel Computing

SP - 219

EP - 226

BT - NPC 2009 - 6th International Conference on Network and Parallel Computing

T2 - NPC 2009 - 6th International Conference on Network and Parallel Computing

Y2 - 19 October 2009 through 21 October 2009

ER -

Search space reduction technique for distributed multiple sequence alignment

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this