Seqanswers Leaderboard Ad

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts
  • Anshuj Garg
    Junior Member
    • Apr 2013
    • 4

    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.
  • GenoMax
    Senior Member
    • Feb 2008
    • 7142

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

    Comment

    • lh3
      Senior Member
      • Feb 2008
      • 686

      #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

      • Anshuj Garg
        Junior Member
        • Apr 2013
        • 4

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

        Comment

        Latest Articles

        Collapse

        • seqadmin
          Pathogen Surveillance with Advanced Genomic Tools
          by seqadmin




          The COVID-19 pandemic highlighted the need for proactive pathogen surveillance systems. As ongoing threats like avian influenza and newly emerging infections continue to pose risks, researchers are working to improve how quickly and accurately pathogens can be identified and tracked. In a recent SEQanswers webinar, two experts discussed how next-generation sequencing (NGS) and machine learning are shaping efforts to monitor viral variation and trace the origins of infectious...
          03-24-2025, 11:48 AM
        • seqadmin
          New Genomics Tools and Methods Shared at AGBT 2025
          by seqadmin


          This year’s Advances in Genome Biology and Technology (AGBT) General Meeting commemorated the 25th anniversary of the event at its original venue on Marco Island, Florida. While this year’s event didn’t include high-profile musical performances, the industry announcements and cutting-edge research still drew the attention of leading scientists.

          The Headliner
          The biggest announcement was Roche stepping back into the sequencing platform market. In the years since...
          03-03-2025, 01:39 PM

        ad_right_rmr

        Collapse

        News

        Collapse

        Topics Statistics Last Post
        Started by seqadmin, 03-20-2025, 05:03 AM
        0 responses
        49 views
        0 reactions
        Last Post seqadmin  
        Started by seqadmin, 03-19-2025, 07:27 AM
        0 responses
        57 views
        0 reactions
        Last Post seqadmin  
        Started by seqadmin, 03-18-2025, 12:50 PM
        0 responses
        50 views
        0 reactions
        Last Post seqadmin  
        Started by seqadmin, 03-03-2025, 01:15 PM
        0 responses
        201 views
        0 reactions
        Last Post seqadmin  
        Working...