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
Published on: July 8, 2025
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.
Abstract:
Genome assembly is one of the most important problems in computational genomics. Here, we suggest addressing an issue that arises in homology-based scaffolding, that is, when linking and ordering contigs to obtain larger pseudo-chromosomes by means of a second incomplete assembly of a related species. The idea is to use alignments of binned regions in one contig to find the most homologous contig in the other assembly. We show that ordering the contigs of the other assembly can be expressed by a new string problem, the longest run subsequence problem (LRS). We show that LRS is NP-hard and present reduction rules and two algorithmic approaches that, together, are able to solve large instances of LRS to provable optimality. All data used in the experiments as well as our source code are freely available. We demonstrate its usefulness within an existing larger scaffolding approach by solving realistic instances resulting from partial Arabidopsis thaliana assemblies in short computation time.
More Related Videos
Related Concept Videos
Evolutionary Relationships through Genome Comparisons
Genome Annotation and Assembly
Conservation of Protein Domains Over Different Proteins
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Multi-species Conserved Sequences
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Protein Families

