SEQanswers

Go Back   SEQanswers > Bioinformatics > Bioinformatics



Similar Threads
Thread Thread Starter Forum Replies Last Post
DEXSeq error in estimateDispersions: match.arg(start.method, c("log(y)", "mean")) fpadilla Bioinformatics 14 07-03-2013 03:11 PM
raw data of paper "The evolution of gene expression levels in mammalian organs" rzhang Illumina/Solexa 5 02-27-2012 06:08 PM
A Lack of an "Original" SOLiD Paper--why? SamCurt SOLiD 5 11-07-2011 09:17 AM
The position file formats ".clocs" and "_pos.txt"? Ist there any difference? elgor Illumina/Solexa 0 06-27-2011 08:55 AM
Paper: "Rapid whole-genome mutational profiling using next-gen technolgies" ECO Literature Watch 7 10-06-2008 06:59 AM

Reply
 
Thread Tools
Old 10-02-2013, 07:55 AM   #1
kenneth_chiu
Junior Member
 
Location: New York

Join Date: Oct 2013
Posts: 2
Default "Multiplicity" in 2001 Pevzner EULER paper

I have a question about exactly how the multiplicity of an edge in the de Bruijn graph is determined. It seems that the multiplicity is simply the number of reads which covers an edge.

However, this seems to not be the complete story. Later, the paper goes on to discuss x,y-detachment. At the bottom of page 9752, left column, they state:
The second condition implies that the Eulerian Superpath
Problem has no solution, because P, Px,y1, and Px,y2 impose
three different scenarios for just two visits of the edge x.
My assumption here is that each of these paths is a read. Thus, there are three reads. Thus, the multiplicity of x would always be three. In other words, this second condition can never occur in a graph that was created from a set of reads, because there would be three visits (multiplicity three), rather than two visits.

What am I missing?

The paper is here.
kenneth_chiu is offline   Reply With Quote
Old 10-03-2013, 10:18 AM   #2
timydaley
Member
 
Location: Los Angeles

Join Date: Jun 2010
Posts: 26
Default

Each node is a distinct (k-1)-mer and the paths are k-mers connecting different paths. They may lie on the same read or on multiple reads.

Consider the following example, using 3-mers. We have 3 6-bp reads: ATATAT, ATATGC, GCTATA. We have the following distinct 2-mers: AT, TA, TG, GC, and CT. AT -> TA (by ATA), AT -> TG (by ATG), TG -> GC (by TGC), GC -> CT (by GCT), CT -> TA (by CTA), and TA -> AT (by TAT).

In actual practice, this gets more complicated by including reverse compliments and self loops (i.e. AA -> AA (by AAA)).

What Pezner is referring to here is if you have one entrance and two exits from a node. You know that there is only one way to visit the node x, but observe two exits. This can't happen if you only visit the node once.

Last edited by timydaley; 10-03-2013 at 10:23 AM.
timydaley is offline   Reply With Quote
Old 10-04-2013, 03:32 PM   #3
kenneth_chiu
Junior Member
 
Location: New York

Join Date: Oct 2013
Posts: 2
Default

Quote:
What Pezner is referring to here is if you have one entrance and two exits from a node. You know that there is only one way to visit the node x, but observe two exits. This can't happen if you only visit the node once.
Hm...that would be if a node had in-total-multiplicity of 1, and and out-total-multiplicity of 2, correct? That's not the case in Fig. 5b, though. In fact, in Fig. 5b, the multiplicities don't seem to match the paths. My understanding is that in that figure, there are three paths corresponding to three reads. In that case, the multiplicity of edge x should be 3, not 2, correct?
kenneth_chiu is offline   Reply With Quote
Reply

Tags
algorithms, euler, pevzner

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off




All times are GMT -8. The time now is 12:12 AM.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Single Sign On provided by vBSSO