The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
OPTIMAL, EFFICIENT RECONSTRUCTION OF PHYLOGENETIC NETWORKS WITH CONSTRAINED RECOMBINATION
Abstract
A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not tree-like. In a seminal paper, Wang et al.1 studied the problem of constructing a phylogenetic network, allowing recombination between sequences, with the constraint that the resulting cycles must be disjoint. We call such a phylogenetic network a "galled-tree". They gave a polynomial-time algorithm that was intended to determine whether or not a set of sequences could be generated on galled-tree. Unfortunately, the algorithm by Wang et al.1 is incomplete and does not constitute a necessary test for the existence of a galled-tree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galled-tree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiple-crossover recombinations. We also prove that when there is a galled-tree for the data, the galled-tree minimizing the number of recombinations is "essentially unique". We also note two additional results: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation per site is allowed; second, the site compatibility problem (which is NP-hard in general) can be solved in polynomial time for any set of sequences that can be derived on a galled tree. Perhaps more important than the specific results about galled-trees, we introduce an approach that can be used to study recombination in general phylogenetic networks. This paper greatly extends the conference version that appears in an earlier work.8 PowerPoint slides of the conference talk can be found at our website.7
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Hudson, R. R., & Kaplan, N. L. (1985) · Genetics · doi:10.1093/genetics/111.1.147 · Cited by 1,555
Cited by
Horizontal gene transfer, genome innovation and evolution
Gogarten, J. P., & Townsend, J. P. (2005) · Nature Reviews Microbiology · doi:10.1038/nrmicro1204 · Cited by 1,020
Inferring whole-genome histories in large population datasets
Kelleher, J., Wong, Y., Wohns, A. W., Fadil, C., Albers, P. K., & McVean, G. (2019) · Nature Genetics · doi:10.1038/s41588-019-0483-y · Cited by 313
Chan, J. M., Carlsson, G., & Rabadan, R. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1313480110 · Cited by 269
Constructing Minimal Ancestral Recombination Graphs
Song, Y. S., & Hein, J. (2005) · Journal of Computational Biology · doi:10.1089/cmb.2005.12.147 · Cited by 130
Mapping Trait Loci by Use of Inferred Ancestral Recombination Graphs
Minichiello, M. J., & Durbin, R. (2006) · The American Journal of Human Genetics · doi:10.1086/508901 · Cited by 115
Metadata
- Authors
- GUSFIELD, D., EDDHU, S., & LANGLEY, C.
- Venue
- Journal of Bioinformatics and Computational Biology
- Publisher
- World Scientific Pub Co Pte Lt
- Published
- 2004-03
- Volume
- 02
- Issue
- 01
- Pages
- 173-213
- ISSN
- 0219-7200 (ISSN-L)
- 1757-6334
- OpenAlex
- W2110570734
- Cited by
- 199
- References
- 1
- FWCI
- 7.65
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: OPTIMAL, EFFICIENT RECONSTRUCTION OF PHYLOGENETIC NETWORKS WITH CONSTRAINED RECOMBINATION. https://app.cochat.ai/papers/10.1142/s0219720004000521
- The paper
- GUSFIELD, D., EDDHU, S., & LANGLEY, C. (2004). OPTIMAL, EFFICIENT RECONSTRUCTION OF PHYLOGENETIC NETWORKS WITH CONSTRAINED RECOMBINATION. Journal of Bioinformatics and Computational Biology. https://doi.org/10.1142/s0219720004000521
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.