SpringerLink
Log in

Homology to Sequence Alignment, From

  • Reference work entry
Encyclopedia of Parallel Computing

  • 225 Accesses

Discussion

Two sequences are considered to be homologous if they share a common ancestor. Sequences are either homologous or nonhomologous, but not in-between [13]. Determining whether two sequences are actually homologous can be a challenging task, as it requires inferences to be made between the sequences. Further complicating this task is the potential that the sequences may appear to be related via chance similarity rather than via common ancestry.

One approach toward determining homology entails the use of sequence-alignment algorithms that maximize the similarity between two sequences. For homology modeling, these alignments could be used to obtain the likely amino-acid correspondence between the sequences.

Introduction

Sequence alignment identifies similarities between a pair of biological sequences (i.e., pairwise sequence alignment) or across a set of multiple biological sequences (i.e., multiple sequence alignment). These alignments, in turn, enable the inference of...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 1,600.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 1,799.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Bibliography

  1. Aji AM, Feng W, Blagojevic F, Nikolopoulos DS (2008) Cell-SWat: modeling and scheduling wavefront computations on the cell broadband engine. In: CF ’08: Proceedings of the 5th conference on computing frontiers. ACM, New York, pp 13–22

    Google Scholar 

  2. Altschul S, Gish W, Miller W, Myers E, Lipman D (1990) Basic local alignment search tool. J Mol Biol 215(3):403–410

    Google Scholar 

  3. Altschul S, Madden T, Schffer A, Zhang J, Zhang Z, Miller W, Lipman D (1997) Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res 25(17):3389–3402

    Article  Google Scholar 

  4. Aluru S, Futamura N, Mehrotra K (2003) Parallel biological sequence comparison using prefix computations. J Parallel Distrib Comput 63:264–272

    Article  MATH  Google Scholar 

  5. Chaichoompu K, Kittitornkun S, Tongsima S (2006) MT-ClustalW: multithreading multiple sequence alignment. In: International parallel and distributed processing symposium. Rhodes Island, Greece, p 280

    Google Scholar 

  6. Darling A, Carey L, Feng W (2003) The design, implementation, and evaluation of mpiBLAST. In: Proceedings of the ClusterWorld conference and Expo, in conjunction with the 4th international conference on Linux clusters: The HPC revolution 2003, San Jose

    Google Scholar 

  7. Di Tommaso P, Orobitg M, Guirado F, Cores F, Espinosa T, Notredame C (2010) Cloud-Coffee: implementation of a parallel consistency-based multiple alignment algorithm in the T-Coffee package and its benchmarking on the Amazon Elastic-Cloud. Bioinformatics 26(15):1903–1904

    Article  Google Scholar 

  8. Do CB, Mahabhashyam MS, Brudno M, Batzoglou S (2005) ProbCons: probabilistic consistency-based multiple sequence alignment. Genome Res 15(2):330–340

    Article  Google Scholar 

  9. Ebedes J, Datta A (2004) Multiple sequence alignment in parallel on a workstation cluster. Bioinformatics 20(7):1193–1195

    Article  Google Scholar 

  10. Edgar R (2004) MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics 5(1):113

    Article  Google Scholar 

  11. Edmiston EE, Core NG, Saltz JH, Smith RM (1989) Parallel processing of biological sequence comparison algorithms. Int J Parallel Program 17:259–275

    Article  MathSciNet  Google Scholar 

  12. Feng DF, Doolittle RF (1987) Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J Mol Evol 25(4):351–360

    Article  Google Scholar 

  13. Fitch W, Smith T (1983) Optimal sequences alignments. Proc Natl Acad Sci 80:1382–1386

    Article  Google Scholar 

  14. Hennessy JL, Patterson DA (2006) Computer architecture: a quantitative approach, 4th edn. Morgan Kaufmann Publishers, San Francisco

    MATH  Google Scholar 

  15. Hirschberg DS (1975) A linear space algorithm for computing maximal common subsequences. Commun ACM 18: 341–343

    Article  MATH  MathSciNet  Google Scholar 

  16. Huang X (1990) A space-efficient parallel sequence comparison algorithm for a message-passing multiprocessor. Int J Parallel Program 18:223–239

    Article  Google Scholar 

  17. Li K (2003) W-MPI: ClustalW analysis using distributed and parallel computing. Bioinformatics 19(12):1585–1586

    Article  Google Scholar 

  18. Li I, Shum W, Truong K (2007) 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA). BMC Bioinformatics 8(1):185

    Article  Google Scholar 

  19. Lin H, Ma X, Chandramohan P, Geist A, Samatova N (2005) Efficient data access for parallel BLAST. In: Proceedings of the 19th IEEE international parallel and distributed processing symposium (IPDPS’05). IEEE Computer Society, Los Alamitos

    Google Scholar 

  20. Lin H, Ma X, Feng W, Samatova NF (2010) Coordinating computation and I/O in massively parallel sequence search. IEEE Trans Parallel Distrib Syst 99:529–543

    Google Scholar 

  21. Lipman D, Pearson W (1988) Improved toolsW, HT for biological sequence comparison. Proc Natl Acad Sci 85(8):2444–2448

    Article  Google Scholar 

  22. Liu W, Schmidt B, Voss B, Müller-Wittig W (2006) GPU-ClustalW: using graphics hardware to accelerate multiple sequence alignment, Chapter 37 In: Robert Y, Parashar M, Badrinath R, Prasanna VK (eds) High performance computing – HiPC 2006. Lecture notes in computer science, vol 4297. Springer, Berlin/Heidelberg, pp 363–374

    Google Scholar 

  23. Liu Y, Maskell D, Schmidt B (2009) CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Res Notes 2(1):73

    Article  Google Scholar 

  24. Liu Y, Schmidt B, Maskell DL (2009) MSA-CUDA: multiple sequence alignment on graphics processing units with CUDA. In: ASAP ’09: Proceedings of the 2009 20th IEEE international conference on application-specific systems, architectures and processors, Washington, DC. IEEE Computer Society, Los Alamitos, California, USA, pp 121–128

    Google Scholar 

  25. Lu W, Jackson J, Barga R (2010) AzureBlast: a case study of cloud computing for science applications. In: 1st workshop on scientific cloud computing, co-located with ACM HPDC 2010 (High performance distributed computing). Chicago, Illinois, USA

    Google Scholar 

  26. Mahram A, Herbordt MC (2010) Fast and accurate NCBI BLASTP: acceleration with multiphase FPGA-based prefiltering. In: Proceedings of the 24th ACM international conference on supercomputing. Tsukuba, Ibaraki, Japan

    Google Scholar 

  27. May J (2001) Parallel I/O for high performance computing. Morgan Kaufmann Publishers, San Francisco

    Google Scholar 

  28. Message Passing Interface Forum (1955) MPI: message-passing interface standard

    Google Scholar 

  29. Message Passing Interface Forum (1977) MPI-2 extensions to the message-passing standard

    Google Scholar 

  30. Mikhailov D, Cofer H, Gomperts R (2001) Performance optimization of Clustal W: parallel Clustal W, HT Clustal, and MULTICLUSTAL. White Papers, Silicon Graphics, Mountain View

    Google Scholar 

  31. Myers EW, Miller W (1988) Optimal alignments in linear space. Comput Appl Biosci (CABIOS) 4(1):11–17

    Google Scholar 

  32. Notredame C (2000) T-coffee: a novel method for fast and accurate multiple sequence alignment. J Mol Biol 302(1):205–217

    Article  Google Scholar 

  33. Oehmen C, Nieplocha J (2006) ScalaBLAST: a scalable implementation of BLAST for high-performance data-intensive bioinformatics analysis. IEEE Trans Parallel Distrib Syst 17(8):740–749

    Article  Google Scholar 

  34. Orobitg M, Guirado F, Notredame C, Cores F (2009) Exploiting parallelism on progressive alignment methods. J Supercomput 1–9. doi: 10.1007/s11227-009-0359-5

    Google Scholar 

  35. Pei J, Sadreyev R, Grishin NV (2003) PCMA: fast and accurate multiple sequence alignment based on profile consistency. Bioinformatics 19(3):427–428

    Article  Google Scholar 

  36. Polychronopoulos CD, Kuck DJ (1987) Guided self-scheduling: a practical scheduling scheme for parallel supercomputers. IEEE Trans Comput 36:1425–1439

    Article  Google Scholar 

  37. Rajko S, Aluru S (2004) Space and time optimal parallel sequence alignments. IEEE Trans Parallel Distrib Syst 15:1070–1081

    Article  Google Scholar 

  38. Rognes T, Seeberg E (2000) Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics 16(8):699–706

    Article  Google Scholar 

  39. Sachdeva V, Kistler M, Speight E, Tzeng TK (2008) Exploring the viability of the cell broadband engine for bioinformatics applications. Parallel Comput 34(11):616–626

    Article  Google Scholar 

  40. Saitou N, Nei M (1987) The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol 4(4):406–425

    Google Scholar 

  41. Sandes EFO, de Melo ACMA (2010) CUDAlign: using GPU to accelerate the comparison of megabase genomic sequences. SIGPLAN Not 45(5):137–146

    Google Scholar 

  42. Sarje A, Aluru S (2009) Parallel genomic alignments on the cell broadband engine. IEEE Trans Parallel Distrib Syst 20(11): 1600–1610

    Article  Google Scholar 

  43. Sneath PH, Sokal RR (1962) Numerical taxonomy. Nature 193:855–860

    Article  Google Scholar 

  44. Thakur R, Choudhary A (1996) An extended two-phase method for accessing sections of out-of-core arrays. Sci Program 5(4): 301–317

    Google Scholar 

  45. Thakur R, Gropp W, Lusk W (1999) Data sieving and collective I/O in ROMIO. In: Symposium on the frontiers of massively parallel processing. Annapolis, Maryland, USA, p 182

    Google Scholar 

  46. Thakur R, Gropp W, Lusk E (1999) On implementing MPI-IO portably and with high performance. In: Proceedings of the sixth workshop on I/O in parallel and distributed systems. Atlanta, Georgia, USA

    Google Scholar 

  47. Thompson JD, Higgins DG, Gibson TJ (1994) CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res 22(22):4673–4680

    Article  Google Scholar 

  48. Vouzis PD, Sahinidis NV (2011) GPU-BLAST: using graphics processors to accelerate protein sequence alignment. Bioinformatics 27(2):182–188

    Article  Google Scholar 

  49. Wallace IM, Orla O, Higgins DG (2005) Evaluation of iterative alignment algorithms for multiple alignment. Bioinformatics 21(8):1408–1414

    Article  Google Scholar 

  50. Wozniak A (1997) Using video-oriented instructions to speed up sequence comparison. Comput Appl Biosci 13(2):145–150

    Google Scholar 

  51. ** of dynamic programming onto a graphics processing unit. In: ICPADS ’09: proceedings of the 2009 15th international conference on parallel and distributed systems, Washington, DC. IEEE Computer Society, Los Alamitos, California, USA, pp 26–33

    Google Scholar 

  52. **ao S, Lin H, Feng W (2011) Characterizing and optimizing protein sequence search on the GPU. In: Proceedings of the 19th IEEE international parallel and distributed processing symposium Anchorage, Alaska. IEEE Computer Society, Los Alamitos, California, USA

    Google Scholar 

  53. Zola J, Yang X, Rospondek A, Aluru S (2007) Parallel-TCoffee: a parallel multiple sequence aligner. In: ISCA international conference on parallel and distributed computing systems (ISCA PDCS 2007), pp 248–253

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Department of Electrical & Computer Engineering, Virginia Tech, Blacksburg, VA, USA

    Wu-Chun Feng (Dr.)

  2. Department of Cancer Biology and Translational Science Institute, School of Medicine, Wake Forest University, Winston-Salem, NC, USA

    Wu-Chun Feng (Dr.)

  3. Department of Computer Science, Virginia Tech, Blacksburg, VA, USA

    Heshan Lin (Dr.)

Authors
  1. Wu-Chun Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wu-Chun Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Heshan Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Illinois at Urbana-Champaign, Urbana, IL, USA

    David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer Science+Business Media, LLC

About this entry

Cite this entry

Feng, WC., Feng, WC., Lin, H. (2011). Homology to Sequence Alignment, From. In: Padua, D. (eds) Encyclopedia of Parallel Computing. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-09766-4_407

Download citation

Publish with us

Policies and ethics

Search

Navigation