Related Experiment Video
Updated: Aug 23, 2025
09:40
Novel Sequence Discovery by Subtractive Genomics
Published on: January 25, 2019
8.7K
On a greedy approach for genome scaffolding
Tom Davot1, Annie Chateau2,3, Rohan Fossé4
1LIRMM, Univ. Montpellier, Montpellier, France. tom.davot@lirmm.fr.
Algorithms for Molecular Biology : AMB
|October 30, 2022
Summary
This study addresses the bioinformatics scaffolding problem, developing a novel approximation algorithm for non-complete graphs. The new method outperforms existing approaches on simulated data, advancing genome assembly techniques.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Scaffolding is a critical bioinformatics problem in genome assembly.
- It involves determining the order and orientation of DNA contigs.
- The problem is analogous to finding paths and cycles in a scaffold graph.
Purpose of the Study:
- To investigate the computational complexity of the scaffolding problem.
- To develop a novel approximation algorithm for scaffolding on non-complete graphs.
Main Methods:
- Analysis of NP-hardness and inapproximability for the scaffolding problem.
- Adaptation of a greedy approximation algorithm for complete graphs to non-complete graphs.
- Development of the first polynomial-time approximation algorithm for scaffolding on non-complete graphs.
Main Results:
- Established NP-hardness and inapproximability results for the scaffolding problem.
- Introduced a novel greedy approximation algorithm applicable to a class of non-complete scaffold graphs.
- Demonstrated that the new algorithm is the first polynomial-time approximation algorithm for this problem on non-complete graphs.
Conclusions:
- The developed approximation algorithm offers improved performance compared to methods designed for complete graphs.
- Tests on simulated data confirm the algorithm's effectiveness in scaffolding.
- This work contributes a significant advancement in computational approaches to genome assembly.
More Related Videos
12:08Hybrid De Novo Genome Assembly for the Generation of Complete Genomes of Urinary Bacteria using Short- and Long-read Sequencing Technologies
Published on: August 20, 2021
5.2K
08:03Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
2.3K
Related Concept Videos
03:36Genome Annotation and Assembly
19.2K
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.2K
02:54Evolutionary Relationships through Genome Comparisons
6.1K
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.1K
02:37Gene Duplication and Divergence
6.3K
The seminal work of Ohno in 1970 popularized the idea of gene duplication and divergence. DNA sequence comparison studies reveal that a large portion of the genes in bacteria, archaebacteria, and eukaryotes was generated by gene duplication and divergence, indicating its critical role in evolution.
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are...
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are...
6.3K
00:58Genomic DNA in Eukaryotes
47.5K
Eukaryotes have large genomes compared to prokaryotes. To fit their genomes into a cell, eukaryotic DNA is packaged extraordinarily tightly inside the nucleus. To achieve this, DNA is tightly wound around proteins called histones, which are packaged into nucleosomes that are joined by linker DNA and coil into chromatin fibers. Additional fibrous proteins further compact the chromatin, which is recognizable as chromosomes during certain phases of cell division.
47.5K
02:02Genomics
36.9K
Genomics is the science of genomes: it is the study of all the genetic material of an organism. In humans, the genome consists of information carried in 23 pairs of chromosomes in the nucleus, as well as mitochondrial DNA. In genomics, both coding and non-coding DNA is sequenced and analyzed. Genomics allows a better understanding of all living things, their evolution, and their diversity. It has a myriad of uses: for example, to build phylogenetic trees, to improve productivity and...
36.9K
01:57Sanger Sequencing
756.0K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
756.0K