Efficient parallel algorithm for optimal three-sequences alignment

Yuan Lin Chun, Tai Huang Chen, Yeh Ching Chung, Yi Tang Chuan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

Sequence alignment is a fundamental problem in the computational biology. Many alignment methods have been proposed in the literature, such as pair-wise sequence alignment (2SA), syntenic alignment, multiple sequence alignment (MSA) and constraint multiple sequence alignment, etc. Three-sequence alignment (3SA) problem has been proposed and discussed in the computational biology and proved that the alignment results from 3SA are better than those from 2SA under some conditions. However, 3SA problem is less discussed over the past decade due to the computer capability. 3SA problem now is worthy to discuss due to the powerful computer and more and more genome and protein sequences. In this paper, an efficient parallel algorithm (P3SA) is proposed to solve 3SA problem. The P3SA method requires O(n2/p) space complexity and O(n3/p) time complexity. The experimental results show that P3SA algorithm is applicable and achieves a satisfied speed-up.

Original languageEnglish
Title of host publication2007 International Conference on Parallel Processing, ICPP
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages14-21
Number of pages8
ISBN (Print)076952933X, 9780769529332
DOIs
StatePublished - 2007
Externally publishedYes
Event36th International Conference on Parallel Processing in Xi'an, ICPP - Xi'an, China
Duration: 10 09 200714 09 2007

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Conference

Conference36th International Conference on Parallel Processing in Xi'an, ICPP
Country/TerritoryChina
CityXi'an
Period10/09/0714/09/07

Keywords

  • Computational biology
  • Dynamic programming
  • Hirschberg's technique
  • Sequence alignment
  • Time and space complexities

Fingerprint

Dive into the research topics of 'Efficient parallel algorithm for optimal three-sequences alignment'. Together they form a unique fingerprint.

Cite this