Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023 Mar 24;18(3):e0281824.
doi: 10.1371/journal.pone.0281824. eCollection 2023.

A complete theoretical framework for inferring horizontal gene transfers using partial order sets

Nahla A Belal  1 , Lenwood S Heath  2
Affiliations

A complete theoretical framework for inferring horizontal gene transfers using partial order sets

Nahla A Belal et al. PLoS One. .

Abstract

We present a method for detecting horizontal gene transfer (HGT) using partial orders (posets). The method requires a poset for each species/gene pair, where we have a set of species S, and a set of genes G. Given the posets, the method constructs a phylogenetic tree that is compatible with the set of posets; this is done for each gene. Also, the set of posets can be derived from the tree. The trees constructed for each gene are then compared and tested for contradicting information, where a contradiction suggests HGT.

PubMed Disclaimer

Conflict of interest statement

The authors have declared that no competing interests exist.

Figures

Fig 1
Fig 1. The possible HGT events for the example in Fig 34.
Fig 2
Fig 2. A trivial non-binary S-tree with a minimum number of nodes and no evolutionary assumptions [3].
Fig 3
Fig 3. An evolutionary S-tree with 5 taxa [3].
Fig 4
Fig 4. Refinement of T1 to T2 [3].
Fig 5
Fig 5. An example of a Hasse diagram.
Fig 6
Fig 6. An example of a tree to test compatibility with posets [3].
Fig 7
Fig 7. An example of a poset compatible with the tree in Fig 6 [3].
Fig 8
Fig 8. An example of a poset incompatible with the tree in Fig 6 [3].
Fig 9
Fig 9. An undirected graph with cliques representing siblings.
Fig 10
Fig 10. Diagram for posets [3].
Fig 11
Fig 11. An undirected graph corresponding to the matrix shown in Table 2.
Fig 12
Fig 12. Tree corresponding to the posets in Fig 10.
Fig 13
Fig 13. Diagrams for posets.
Fig 14
Fig 14. Tree corresponding to the posets in Fig 13.
Fig 15
Fig 15. Set of posets P for the set of species S = {s1, s2, s3, s4, s5}.
Fig 16
Fig 16. The tree corresponding to the set of posets P in Fig 15.
Fig 17
Fig 17. Algorithm to construct an S-tree from a set of posets P={P1,P2,…,Pn}.
Fig 18
Fig 18. Algorithm to validate an n × n matrix A.
Fig 19
Fig 19. Algorithm to find the maximum of a matrix A.
Fig 20
Fig 20. Algorithm to find a clique with edge labels equal max.
Fig 21
Fig 21. Algorithm to add elements of a clique as siblings in a tree T.
Fig 22
Fig 22. An example of how the poset corresponding to s1 is generated.
Fig 23
Fig 23. Algorithm to generate a set of posets P from an S-tree T.
Fig 24
Fig 24. Two contradicting trees.
Fig 25
Fig 25. Algorithm to find the minimum common refinement of two trees.
Fig 26
Fig 26. Algorithm to find the 2-partitions set of a given tree.
Fig 27
Fig 27. Algorithm to construct a tree from its 2-partitions set.
Fig 28
Fig 28. Refinement of T1 and T2 into T3.
Fig 29
Fig 29. T3 is the minimum common refinement of T1 and T2.
Fig 30
Fig 30. An example to illustrate the algorithm MinCommonRefine.
Fig 31
Fig 31. An example to illustrate the algorithm ConstructTree2Partitions.
Fig 32
Fig 32. Algorithm to detect contradiction between two trees.
Fig 33
Fig 33. Algorithm to infer HGT.
Fig 34
Fig 34. An example to illustrate the algorithm InferHGT.
See this image and copyright information in PMC

References

    1. Daubin V, Szoellosi GJ. Horizontal Gene Transfer and the History of Life. Cold Spring Harbor Perspectives in Biology. 2016;8. doi: 10.1101/cshperspect.a018036 - DOI - PMC - PubMed
    1. Lake JA, Rivera MC. Deriving the genomic tree of life in the presence of horizontal gene transfer: Conditioned reconstruction. Molecular Biology and Evolution. 2004;21(4):681–690. doi: 10.1093/molbev/msh061 - DOI - PubMed
    1. Belal NA, Heath LS. Inferring horizontal gene transfers from posets. In: 2nd International Conference on Computer Technology and Development, ICCTD 2010; 2010. p. 32–36.
    1. Bailey CD, Fain MG, Houde P. On conditioned reconstruction, gene content data, and the recovery of fusion genomes. Molecular Phylogenetic and Evolution. 2006;39:263–270. doi: 10.1016/j.ympev.2005.11.020 - DOI - PubMed
    1. Bapteste E, Walsh DA. Does the ring of life ring true? Trends in Microbiology. 2005;13(6):256–261. - PubMed