Seqanswers Leaderboard Ad

Collapse

Announcement

Collapse
No announcement yet.
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Assembly using Euler Tour

    Hello,
    I am working on "DNA sequence assembly using Euler tour" problem. The algorithms that use euler tour technique generally involve 4 steps:
    1. K-mer extractions.
    2. De-bruijn graph construction.
    3. Euler tour construction.
    4. Contig Generation.

    I understood till step-2. But the problem is, the graph that is formed using k-mers is not balanced and to find euler tour the graph should be balanced (each vertices in-degree = out-degree). I am not able to understand how the algorithms construct a euler tour when the graph is not balance. Also, the output of a assembler is a set of contigs, How these set of contigs are generated from a single de bruijn graph. How we are getting contigs from euler tour. Please Help.

  • #2
    This thread has some interesting links: http://seqanswers.com/forums/showthread.php?t=21573

    Comment


    • #3
      Finding the Euler tour is only of theoretical interest but of little practical use. So far as I know, most main-stream assemblers do not attempt to find an Eulerian circuit. They just concatenate nodes/edges whose in- and out-degree are both 1. The concatenated segments are contigs. An Eulerian tour gives you the entire genome, in theory, not contigs.

      If you just think a pure theoretical problem, on a de Bruijn graph, you would like to solve a Chinese postman problem, a generalized Eulerian problem. Actually a more proper way is to determine the traversal counts of each edge. There are other theoretical papers on these problems.

      Comment


      • #4
        Thanks a lot for your replies.....

        Comment

        Latest Articles

        Collapse

        • seqadmin
          Essential Discoveries and Tools in Epitranscriptomics
          by seqadmin


          The field of epigenetics has traditionally concentrated more on DNA and how changes like methylation and phosphorylation of histones impact gene expression and regulation. However, our increased understanding of RNA modifications and their importance in cellular processes has led to a rise in epitranscriptomics research. “Epitranscriptomics brings together the concepts of epigenetics and gene expression,” explained Adrien Leger, PhD, Principal Research Scientist on Modified Bases...
          Today, 07:01 AM
        • seqadmin
          Current Approaches to Protein Sequencing
          by seqadmin


          Proteins are often described as the workhorses of the cell, and identifying their sequences is key to understanding their role in biological processes and disease. Currently, the most common technique used to determine protein sequences is mass spectrometry. While still a valuable tool, mass spectrometry faces several limitations and requires a highly experienced scientist familiar with the equipment to operate it. Additionally, other proteomic methods, like affinity assays, are constrained...
          04-04-2024, 04:25 PM

        ad_right_rmr

        Collapse

        News

        Collapse

        Topics Statistics Last Post
        Started by seqadmin, 04-11-2024, 12:08 PM
        0 responses
        37 views
        0 likes
        Last Post seqadmin  
        Started by seqadmin, 04-10-2024, 10:19 PM
        0 responses
        39 views
        0 likes
        Last Post seqadmin  
        Started by seqadmin, 04-10-2024, 09:21 AM
        0 responses
        34 views
        0 likes
        Last Post seqadmin  
        Started by seqadmin, 04-04-2024, 09:00 AM
        0 responses
        54 views
        0 likes
        Last Post seqadmin  
        Working...
        X