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

Subject: Re: [Boost-users] [BGL] SPPRC formulation
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-09-29 17:18:51

On Wed, 29 Sep 2010, Adam Spargo wrote:

> 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 ...

Is there a description somewhere of what you're trying to do at a high 
level?  I still don't completely understand the actual problem you're 
trying to solve.  Are you just looking for paths that minimize the total 
vertex distances, or are there more limitations or objectives that you 
have?

> Yes, the path should be simple.

Could you ever have a situation similar to a negative-weight cycle where 
the "best" overall (not necessarily simple) path is not simple?

-- Jeremiah Willcock