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 Concept Videos

Evolutionary Relationships through Genome Comparisons02:54

Evolutionary Relationships through Genome Comparisons

6.5K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
6.5K
Genome Annotation and Assembly03:36

Genome Annotation and Assembly

19.7K
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
19.7K
Conservation of Protein Domains Over Different Proteins02:26

Conservation of Protein Domains Over Different Proteins

13.4K
Protein domains are small structurally independent units that are part of a single amino acid chain.  Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...
13.4K
Maxam-Gilbert Sequencing01:05

Maxam-Gilbert Sequencing

11.8K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
11.8K
Multi-species Conserved Sequences02:51

Multi-species Conserved Sequences

4.4K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale  studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
4.4K
Protein Families02:47

Protein Families

16.2K
Protein families are groups of homologous proteins; that is, they have similarities in amino acid sequences and three-dimensional structures. Protein families usually occur because of gene duplication, where an additional copy of a gene is inserted into the genome of an organism.   Mutations that change the amino acids but still allow the protein to be properly synthesized, will lead to new protein family members.   If these new proteins contain similar amino acids in key...
16.2K

You might also read

Related Articles

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

Sort by
Same author

Barriers and facilitators to service utilisation and management of sexually transmitted infections in India: a multicentric mixed-method approach study protocol.

BMJ open·2026
Same author

Tracing modern breeding introgressions in European potato.

TAG. Theoretical and applied genetics. Theoretische und angewandte Genetik·2026
Same author

Virus variant quantification with Orthanq.

BMC bioinformatics·2026
Same author

B-GATA factors are required for nitrogen-responsive growth in Physcomitrium patens and Arabidopsis thaliana.

The New phytologist·2026
Same author

Dynamic Mortality Risk Prediction in Myelodysplastic Syndromes Using Longitudinal Clinical Data.

JCO clinical cancer informatics·2025
Same author

Sequence-to-graph alignment based copy number calling using a network flow formulation.

bioRxiv : the preprint server for biology·2025
Same journal

Haplotype-aware long-read error correction.

Algorithms for molecular biology : AMB·2026
Same journal

Extension of partial atom-to-atom maps: uniqueness and algorithms.

Algorithms for molecular biology : AMB·2026
Same journal

Lossless pangenome indexing using tag arrays.

Algorithms for molecular biology : AMB·2026
Same journal

Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer.

Algorithms for molecular biology : AMB·2026
Same journal

Probing transcription factor subsets in gene regulatory networks.

Algorithms for molecular biology : AMB·2026
Same journal

Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features.

Algorithms for molecular biology : AMB·2026
See all related articles

Related Experiment Video

Updated: Oct 31, 2025

Application of I TASSER, trRosetta, UCSF Chimera, HADDOCK server, and HEX loria for De Novo and In Silico Design of Proteins
05:08

Application of I TASSER, trRosetta, UCSF Chimera, HADDOCK server, and HEX loria for De Novo and In Silico Design of Proteins

Published on: July 8, 2025

517

Using the longest run subsequence problem within homology-based scaffolding.

Sven Schrinner1, Manish Goel2,3, Michael Wulfert4

  • 1Algorithmic Bioinformatics, Heinrich Heine University Düsseldorf, Düsseldorf, Germany.

Algorithms for Molecular Biology : AMB
|June 29, 2021
PubMed
Summary
This summary is machine-generated.

This study introduces a novel method for genome assembly scaffolding using homologous contigs from related species. It solves the NP-hard longest run subsequence problem to improve pseudo-chromosome construction.

Keywords:
AlignmentAssemblyLongest subsequenceString algorithm

More Related Videos

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

7.4K
A Protocol for Computer-Based Protein Structure and Function Prediction
16:41

A Protocol for Computer-Based Protein Structure and Function Prediction

Published on: November 3, 2011

69.2K

Related Experiment Videos

Last Updated: Oct 31, 2025

Application of I TASSER, trRosetta, UCSF Chimera, HADDOCK server, and HEX loria for De Novo and In Silico Design of Proteins
05:08

Application of I TASSER, trRosetta, UCSF Chimera, HADDOCK server, and HEX loria for De Novo and In Silico Design of Proteins

Published on: July 8, 2025

517
Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

7.4K
A Protocol for Computer-Based Protein Structure and Function Prediction
16:41

A Protocol for Computer-Based Protein Structure and Function Prediction

Published on: November 3, 2011

69.2K

Area of Science:

  • Computational Genomics
  • Bioinformatics
  • Genome Assembly

Background:

  • Genome assembly is a critical challenge in computational genomics.
  • Homology-based scaffolding links and orders DNA contigs using related species' assemblies.
  • A key issue is efficiently identifying and ordering homologous contigs between assemblies.

Purpose of the Study:

  • To address the challenge of ordering contigs in homology-based scaffolding.
  • To introduce a novel string problem, the longest run subsequence (LRS) problem, for contig ordering.
  • To develop efficient algorithms for solving the LRS problem to optimality.

Main Methods:

  • Utilizing alignments of binned regions to identify homologous contigs between two assemblies.
  • Formulating the contig ordering problem as the longest run subsequence (LRS) problem.
  • Developing reduction rules and two algorithmic approaches to solve large LRS instances.

Main Results:

  • Demonstrated that the LRS problem is NP-hard.
  • Presented algorithms capable of solving large LRS instances to provable optimality.
  • Successfully applied the method to realistic partial *Arabidopsis thaliana* assemblies.

Conclusions:

  • The proposed LRS-based approach effectively solves a critical problem in homology-based scaffolding.
  • The developed algorithms provide efficient and optimal solutions for contig ordering.
  • The method significantly improves genome assembly scaffolding, as shown with *Arabidopsis thaliana* data.