Multiple biological sequence alignment in heterogeneous multicore clusters with user-selectable task allocation policies

详细信息    查看全文

• 作者：Emerson de Araujo?Macedo (1)
  Alba Cristina Magalhaes?Alves?de?Melo (1)
  Gerson Henrique Pfitscher (1)
  Azzedine Boukerche (2) (3)
  
• 关键词：Heterogeneous multicore clusters ; Bioinformatics ; Multiple sequence alignment ; Task allocation policies
• 刊名：The Journal of Supercomputing
• 出版年：2013
• 出版时间：March 2013
• 年：2013
• 卷：63
• 期：3
• 页码：740-756
• 全文大小：717KB
• 参考文献：1. Brudno M, Steinkamp R, Morgenstern B (2004) The CHAOS/DIALIGN WWW server for multiple alignment of genomic sequences. Nucleic Acids Res. 32:41-4. Web Server issue CrossRef
  2. Chaichoompu K, Kittitornkun S, Tongsima S (2006) MT-clustalW: multithreading multiple sequence alignment. In: IPDPS. IEEE Press, New York
  3. ConsortiumTU (2011) Ongoing and future developments at the universal protein resource. Nucleic Acids Res. 39:214-19. Database issue CrossRef
  4. Durbin R, Krigh E, Mitcheson G (1998) Biological sequence analysis. Cambridge University Press, Cambridge CrossRef
  5. Finn D, Mistry J, Tate JG, Coggill C, Heger A, Pollington JE, Gavin L, Gunasekaran P, Ceric G, Forslund K, Holm A, Sonnhammer ELL, Eddy R, Bateman A (2010) The Pfam protein families database. Nucleic Acids Res. 38:211-22. Database issue CrossRef
  6. Higgins DG, Thompson JD, Gibson TJ (1994) ClustalW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix. Nucleic Acids Res. 22:4673-680 CrossRef
  7. Hummel SF, Schmidt JP, Uma RN, Wein J (1996) Load-sharing in heterogeneous systems via weighted factoring. In: SPAA, pp 318-28
  8. Li KB (2003) ClustalW-MPI: ClustalW analysis using distributed and parallel computing. Bioinformatics 19:1585-586 CrossRef
  9. Macedo EA, Melo ACMA, Pfitscher H, Boukerche A (2011) Hybrid MPI/OpenMP strategy for biological multiple sequence alignment with DIALIGN-TX in heterogeneous multicore clusters. In: IPDPS workshops, pp 418-25
  10. Morgenstern B (1999) DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment. Bioinformatics 15:211-18 CrossRef
  11. Morgenstern B, Dress A, Werner T (1996) Multiple DNA and protein sequence alignment based on segment-to-segment comparison. In: Proceedings of the national academy of science, vol?93, pp?12098-2103
  12. Morgenstern B, Frech K, Dress A, Werner T (1998) DIALIGN: finding local similarities by multiple sequence alignment. Bioinformatics 14:290-94 CrossRef
  13. Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Dover, New York
  14. Polychronopoulos CD, Kuck DJ (1987) Guided self-scheduling: a practical scheduling scheme for parallel supercomputers. IEEE Trans. Comput. 36:1425-439 CrossRef
  15. Schmollinger M, Nieselt K, Kaufmann M, Morgenstern B (2004) DIALIGN P: fast pair-wise and multiple sequence alignment using parallel processors. BMC Bioinform. 5:128 CrossRef
  16. Subramanian AR, Kaufmann M, Morgenstern B (2008) DIALIGN-TX: greedy and progressive approaches for segment-based multiple sequence alignment. Algorithm Mol. Biol. 3:6 CrossRef
  17. Tan G, Feng S, Sun N (2005) Parallel multiple sequences alignment in SMP clusters. In: High-performance computing in Asia-Pacific region
  18. Tang P, Yew PC (1986) Processor self-scheduling for multiple-nested parallel loops. In: ICPP conference, pp 528-35
  19. Tzen TH, Ni LM (1993) Trapezoid self-scheduling: a practical scheduling scheme for parallel compilers. IEEE Trans. Parallel Distrib. Syst. 4:87-8 CrossRef
  20. Wang L, Jiang T (1994) On the complexity of multiple sequence alignment. J. Comput. Biol. 4:337-48 CrossRef
  21. Zola J, Yang X, Rospondek A, Aluru S (2007) T-Coffee: a parallel multiple sequence aligner. In: PDCS, pp 248-53
  22. Boukerche A, Correa JM, Melo ACMA, Jacobi RP (2010) A hardware accelerator for the fast retrieval of DIALIGN biological sequence alignments in linear space. IEEE Trans. Comput. 59(6):808-21 CrossRef
  
• 作者单位：Emerson de Araujo?Macedo (1)
  Alba Cristina Magalhaes?Alves?de?Melo (1)
  Gerson Henrique Pfitscher (1)
  Azzedine Boukerche (2) (3)
  
  1. Department of Computer Science, University of Brasilia (UnB), Brasilia, Brazil
  2. School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada
  3. Kuwait University, Kuwait City, Kuwait
  
• ISSN：1573-0484

文摘

Multiple Sequence Alignment (MSA) is an important problem in Bioinformatics that aims to align more than two sequences in order to emphasize similarity regions. This problem is known to be NP-Hard, so heuristic methods are used to solve?it. DIALIGN-TX is an iterative heuristic method for MSA that generates alignments by concatenating ungapped regions with high similarity. Usually, the first phase of MSA algorithms is parallelized by distributing several independent tasks among the nodes. Even though heterogeneous multicore clusters are becoming very common nowadays, very few task allocation policies were proposed for this type of architecture. This paper proposes an MPI/OpenMP master/slave parallel strategy to run DIALIGN-TX in heterogeneous multicore clusters, with several allocation policies. We show that an appropriate choice of the master node has great impact on the overall system performance. Also, the results obtained in a heterogeneous multicore cluster composed of 4 nodes (30?cores), with real sequence sets show that the execution time can be drastically reduced when the appropriate allocation policy is used.