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

A fast parallel algorithm for finding the longest common sequence of multiple biosequences.

Yixin Chen1, Andrew Wan, Wei Liu

  • 1Department of Computer Science and Engineering, Washington University in St, Louis, St, Louis, MO 63130, USA. chen@cse.wustl.edu

BMC Bioinformatics
|January 16, 2007
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

A risk-based approach can guide safe cell line development and cell banking for scaled-up cultivated meat production.

Nature food·2025
Same author

ASXL1 truncating variants in BOS and myeloid leukemia drive shared disruption of Wnt-signaling pathways but have differential isoform usage of RUNX3.

BMC medical genomics·2024
Same author

Medium-Term Weight Loss and Remission of Comorbidities Following Endoscopic Sleeve Gastroplasty: a Systematic Review and Meta-analysis.

Obesity surgery·2023
Same author

Interventions for Grieving and Bereaved Informal Caregivers: A Scoping Review of the Canadian Literature.

Journal of palliative care·2022
Same author

Support for Informal Caregivers in Canada: A Scoping Review from a Hospice and Palliative/End-of-Life Care Lens.

Journal of palliative care·2022
Same author

The Grief and Bereavement Experiences of Informal Caregivers: A Scoping Review of the North American Literature.

Journal of palliative care·2021

FAST_LCS is a novel parallel algorithm that significantly speeds up the computation of the longest common sequence (LCS) for multiple biosequences. This bioinformatics tool offers optimal efficiency compared to existing methods.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Development

Background:

  • The longest common sequence (LCS) problem is fundamental in bioinformatics.
  • Existing methods for multiple biosequence LCS computation can be computationally intensive.

Purpose of the Study:

  • To present a novel, fast parallel algorithm named FAST_LCS.
  • To accelerate the computation of the longest common sequence (LCS) for multiple biosequences.

Main Methods:

  • Constructs a novel successor table to identify identical pairs and their levels.
  • Utilizes traceback from identical character pairs for LCS determination.
  • Employs effective pruning techniques to reduce computational complexity.

Main Results:

Related Experiment Videos

  • The FAST_LCS algorithm demonstrates optimal performance.
  • Achieves significantly higher efficiency compared to leading LCS algorithms.
  • Experimental validation on gene sequences from the TIGR database confirms efficiency.

Conclusions:

  • Developed one of the fastest parallel LCS algorithms for MPP computing.
  • Achieves O(L) sequential and O(|LCS(X, Y)|) parallel time complexity for two sequences.
  • Achieves O(L) sequential and O(|LCS(X1, ..., Xn)|) parallel time complexity for n sequences.