Limits...
A minimal descriptor of an ancestral recombinations graph.

Parida L, Palamara PF, Javed A - BMC Bioinformatics (2011)

Bottom Line: Its structure-preserving characteristic ensures that all the branch lengths of the marginal trees of the minimal descriptor ARG are identical to that of G and the samples-preserving property asserts that the patterns of genetic variation in the samples of the minimal descriptor ARG are exactly the same as that of G.Based on the definition of this lossless and bounded structure, we derive local properties of the vertices of a minimal descriptor ARG, which lend itself very naturally to the design of efficient sampling algorithms.We further show that a class of minimal descriptors, that of binary ARGs, models the standard coalescent exactly (Thm 6).

View Article: PubMed Central - HTML - PubMed

Affiliation: Computational Genomics, IBM T J Watson Research, Yorktown, New York, USA. parida@us.ibm.com

ABSTRACT

Background: Ancestral Recombinations Graph (ARG) is a phylogenetic structure that encodes both duplication events, such as mutations, as well as genetic exchange events, such as recombinations: this captures the (genetic) dynamics of a population evolving over generations.

Results: In this paper, we identify structure-preserving and samples-preserving core of an ARG G and call it the minimal descriptor ARG of G. Its structure-preserving characteristic ensures that all the branch lengths of the marginal trees of the minimal descriptor ARG are identical to that of G and the samples-preserving property asserts that the patterns of genetic variation in the samples of the minimal descriptor ARG are exactly the same as that of G. We also prove that even an unbounded G has a finite minimal descriptor, that continues to preserve certain (graph-theoretic) properties of G and for an appropriate class of ARGs, our estimate (Eqn 8) as well as empirical observation is that the expected reduction in the number of vertices is exponential.

Conclusions: Based on the definition of this lossless and bounded structure, we derive local properties of the vertices of a minimal descriptor ARG, which lend itself very naturally to the design of efficient sampling algorithms. We further show that a class of minimal descriptors, that of binary ARGs, models the standard coalescent exactly (Thm 6).

Show MeSH
(a) Non-gapped segments (b) Gapped segments t-coalescent vertex v: Five cases are shown where the total number of junctions does not increase with coalescence. The white segments represent the gaps whereas the colored segments refer to the non-mixing segments. (a) Two cases with non-gapped segments. (b) Three cases with gapped segments.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3044314&req=5

Figure 11: (a) Non-gapped segments (b) Gapped segments t-coalescent vertex v: Five cases are shown where the total number of junctions does not increase with coalescence. The white segments represent the gaps whereas the colored segments refer to the non-mixing segments. (a) Two cases with non-gapped segments. (b) Three cases with gapped segments.

Mentions: Some preliminary results from our implementation is shown in Figs 11, 12, 13 for the interested reader.


A minimal descriptor of an ancestral recombinations graph.

Parida L, Palamara PF, Javed A - BMC Bioinformatics (2011)

(a) Non-gapped segments (b) Gapped segments t-coalescent vertex v: Five cases are shown where the total number of junctions does not increase with coalescence. The white segments represent the gaps whereas the colored segments refer to the non-mixing segments. (a) Two cases with non-gapped segments. (b) Three cases with gapped segments.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3044314&req=5

Figure 11: (a) Non-gapped segments (b) Gapped segments t-coalescent vertex v: Five cases are shown where the total number of junctions does not increase with coalescence. The white segments represent the gaps whereas the colored segments refer to the non-mixing segments. (a) Two cases with non-gapped segments. (b) Three cases with gapped segments.
Mentions: Some preliminary results from our implementation is shown in Figs 11, 12, 13 for the interested reader.

Bottom Line: Its structure-preserving characteristic ensures that all the branch lengths of the marginal trees of the minimal descriptor ARG are identical to that of G and the samples-preserving property asserts that the patterns of genetic variation in the samples of the minimal descriptor ARG are exactly the same as that of G.Based on the definition of this lossless and bounded structure, we derive local properties of the vertices of a minimal descriptor ARG, which lend itself very naturally to the design of efficient sampling algorithms.We further show that a class of minimal descriptors, that of binary ARGs, models the standard coalescent exactly (Thm 6).

View Article: PubMed Central - HTML - PubMed

Affiliation: Computational Genomics, IBM T J Watson Research, Yorktown, New York, USA. parida@us.ibm.com

ABSTRACT

Background: Ancestral Recombinations Graph (ARG) is a phylogenetic structure that encodes both duplication events, such as mutations, as well as genetic exchange events, such as recombinations: this captures the (genetic) dynamics of a population evolving over generations.

Results: In this paper, we identify structure-preserving and samples-preserving core of an ARG G and call it the minimal descriptor ARG of G. Its structure-preserving characteristic ensures that all the branch lengths of the marginal trees of the minimal descriptor ARG are identical to that of G and the samples-preserving property asserts that the patterns of genetic variation in the samples of the minimal descriptor ARG are exactly the same as that of G. We also prove that even an unbounded G has a finite minimal descriptor, that continues to preserve certain (graph-theoretic) properties of G and for an appropriate class of ARGs, our estimate (Eqn 8) as well as empirical observation is that the expected reduction in the number of vertices is exponential.

Conclusions: Based on the definition of this lossless and bounded structure, we derive local properties of the vertices of a minimal descriptor ARG, which lend itself very naturally to the design of efficient sampling algorithms. We further show that a class of minimal descriptors, that of binary ARGs, models the standard coalescent exactly (Thm 6).

Show MeSH