Re: [Boost-users] [BGL] SPPRC formulation

Subject: Re: [Boost-users] [BGL] SPPRC formulation
From: Adam Spargo (aws_at_[hidden])
Date: 2010-09-29 05:52:23

Hi, thanks for your reply

>> I would like to use the r_c_shortest_paths algorithm. My constraint is that 
>> given pairs of vertices i, j (each i have a single mate j) must have a 
>> distance between them which is consistent with a given distribution. I am 
>> looking for the path which is most consistent with this distribution. Does 
>> anybody have any experience of formulating such a constraint in BGL?

> I'm not sure what you mean here.  What exactly does "consistent with this 
> distribution" mean?  Is that referring to a probability distribution? Are you 
> trying to find a path that maximizes some property of edge labels? If so, is 
> the path required to be simple (contain each vertex at most once)?

Sorry ... each edge has a length, and pairs of vertices have a 
distance between them (called the insert size), depending on how well the 
DNA library is made the insert size of the pairs has a distribution. All 
we get is the size they were aiming for - we usually assume a normal 
distribution with this size as mean and s.d. of 20% - but this is 
completely arbitrary and is often wrong. I was planning to approximate the 
distribution from parts of my graph without cycles. BUT in the first 
instance implementing a SPPRC with exact insert size could be seen as 
progress ...

Yes, the path should be simple.

>> The second problem is that I am currently modelling the problem with an 
>> undirected graph. The edges could be viewed as bi-directional, but only due 
>> to the double stranded nature of DNA. Once I have started on a path I just 
>> choose the label which is consistent with the direction I am going, but the 
>> graph is essentially undirected, you can always go in either direction down 
>> an edge. Could an undirected graph be used with this algorithm or must I 
>> use a directed graph?
>
> The documentation says that the graph needs to be directed.  However, have 
> you tried it with an undirected graph?  I don't see a reason in the 
> pseudocode that justifies the directedness requirement.

Thanks, I will implement a simple example and try to build up to the real 
problem.

Best,

Adam.

-- 
 The Wellcome Trust Sanger Institute is operated by Genome Research 
 Limited, a charity registered in England with number 1021457 and a 
 company registered in England with number 2742969, whose registered 
 office is 215 Euston Road, London, NW1 2BE.