Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Parallel sequence alignment in limited space

J A Grice1, R Hughey, D Speck

  • 1University of California, Santa Cruz 95064, USA.

Proceedings. International Conference on Intelligent Systems for Molecular Biology
|January 1, 1995
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Achievement of Target Gain Larger than Unity in an Inertial Fusion Experiment.

Physical review letters·2024
Same author

Lawson Criterion for Ignition Exceeded in an Inertial Fusion Experiment.

Physical review letters·2022
Same author

Methods of analysis for 2-dodecylcyclobutanone and studies to support its role as a unique marker of food irradiation.

Food chemistry·2013
Same author

[Specific aspects of vaccine manufacturing].

Annales pharmaceutiques francaises·2009
Same author

Energy function-based approaches to graph coloring.

IEEE transactions on neural networks·2008
Same author

Plasma fibronectin levels and coronary artery disease.

Journal of thrombosis and haemostasis : JTH·2007
Same journal

Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB 2000). San Diego, California, USA. August 19-23, 2000.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2001
Same journal

Analysis of gene expression data with pathway scores.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2000
Same journal

Towards a complete map of the protein space based on a unified sequence and structure analysis of all known proteins.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2000
Same journal

Mining for putative regulatory elements in the yeast genome using gene expression data.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2000
Same journal

A multiple alignment algorithm for metabolic pathway analysis using enzyme hierarchy.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2000
Same journal

Sequence database search using jumping alignments.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2000
See all related articles

This study presents new algorithms for sequence alignment on parallel processors. These methods reduce memory requirements for single-instruction, multiple-data (SIMD) systems, enabling efficient alignment computation.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Design

Background:

  • Sequence comparison is parallelizable on SIMD processors.
  • Sequence alignment, however, is more complex and not suitable for SIMD with local communication.

Purpose of the Study:

  • To propose methods for computing sequence alignments on SIMD processors with limited memory.
  • To develop algorithms suitable for both parallel and serial implementations.

Main Methods:

  • Developed algorithms that reduce space complexity from O(n) to O(L sqrt(n)) per processing element.
  • Introduced a trade-off between slowdown (factor of L) and space requirements.
  • Designed an O(n log n) parallel time algorithm using O(log n) space per SIMD processing element.

Related Experiment Videos

Main Results:

  • Achieved efficient sequence alignment computation on SIMD architectures.
  • Algorithms are adaptable for serial processing.
  • Demonstrated an O(n log n) parallel time complexity with reduced space overhead.

Conclusions:

  • The proposed methods enable efficient sequence alignment on hardware-constrained SIMD systems.
  • These algorithms offer a practical solution for large-scale sequence analysis.
  • The work bridges the gap between theoretical algorithms and practical hardware implementations.