Question: Application Of "Vertex Cover" In Bioinformatics Problems
gravatar for Dana
8.6 years ago by
Dana50 wrote:

A Vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

I understand the vertex cover problem, but how is it used in bioinformatics?

algorithm graph • 3.7k views
ADD COMMENTlink modified 8.4 years ago by Gingi330 • written 8.6 years ago by Dana50

Maybe a better question would be 'has anyone applied this to a bioinformatics problem?'. There are probably multiple useful applications of this theory to bioinformatics. The question is whether anyone has found them!

ADD REPLYlink written 8.6 years ago by Daniel Standage3.9k

I have edited the title of the question.

ADD REPLYlink written 8.6 years ago by Khader Shameer18k
gravatar for Gingi
8.6 years ago by
Irvington, NY
Gingi330 wrote:

The vertex cover problem is the basis for de novo genome assembly using the overlap-consensus method. Assemblers like CABOG, the Celera assembler, construct an overlap graph of many whole-genome shotgun reads, where each vertex correspond to a read and the edges represent mutual overlap between two reads. The assembler then attempts to find a Hamiltonian path through the graph, where each vertex (read) is visited exactly once. The Hamiltonian path then represents the consensus sequence of the generated assembly.

Despite the effectiveness of the overlap-consensus method for long reads (+800 bp), De Bruijn assemblers have recently become the norm for short-read assembly. These assemblers trace an Eulerian path through a De Bruijn graph, where each edge corresponds to a kmer derived from each read and a vertex represents an exact overlap between two kmers.

Read more about genome assembly here. (There is a lot of published literature on this topic, most of it accessible through the links.)

ADD COMMENTlink written 8.6 years ago by Gingi330

I believe that in de Bruijn graph, vertices represent _kmers_ and directed edges connect kmers that overlap by k-1 symbols.

ADD REPLYlink written 5.3 years ago by Lynxoid220
Please log in to add an answer.


Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 857 users visited in the last hour