Predicting horizontal gene transfers with perfect transfer networks
Abstract Background Horizontal gene transfer inference approaches are usually based on gene sequences: parametric methods search for patterns that deviate from a particular genomic signature, while phylogenetic methods use sequences to reconstruct the gene and species trees. However, it is well-know...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2024-02-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s13015-023-00242-2 |
| _version_ | 1797275856315351040 |
|---|---|
| author | Alitzel López Sánchez Manuel Lafond |
| author_facet | Alitzel López Sánchez Manuel Lafond |
| author_sort | Alitzel López Sánchez |
| collection | DOAJ |
| description | Abstract Background Horizontal gene transfer inference approaches are usually based on gene sequences: parametric methods search for patterns that deviate from a particular genomic signature, while phylogenetic methods use sequences to reconstruct the gene and species trees. However, it is well-known that sequences have difficulty identifying ancient transfers since mutations have enough time to erase all evidence of such events. In this work, we ask whether character-based methods can predict gene transfers. Their advantage over sequences is that homologous genes can have low DNA similarity, but still have retained enough important common motifs that allow them to have common character traits, for instance the same functional or expression profile. A phylogeny that has two separate clades that acquired the same character independently might indicate the presence of a transfer even in the absence of sequence similarity. Our contributions We introduce perfect transfer networks, which are phylogenetic networks that can explain the character diversity of a set of taxa under the assumption that characters have unique births, and that once a character is gained it is rarely lost. Examples of such traits include transposable elements, biochemical markers and emergence of organelles, just to name a few. We study the differences between our model and two similar models: perfect phylogenetic networks and ancestral recombination networks. Our goals are to initiate a study on the structural and algorithmic properties of perfect transfer networks. We then show that in polynomial time, one can decide whether a given network is a valid explanation for a set of taxa, and show how, for a given tree, one can add transfer edges to it so that it explains a set of taxa. We finally provide lower and upper bounds on the number of transfers required to explain a set of taxa, in the worst case. |
| first_indexed | 2024-03-07T15:20:01Z |
| format | Article |
| id | doaj.art-7b57b69e6c1e45348bd704c8433f9cfc |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-03-07T15:20:01Z |
| publishDate | 2024-02-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-7b57b69e6c1e45348bd704c8433f9cfc2024-03-05T17:41:30ZengBMCAlgorithms for Molecular Biology1748-71882024-02-0119111910.1186/s13015-023-00242-2Predicting horizontal gene transfers with perfect transfer networksAlitzel López Sánchez0Manuel Lafond1Department of Computer Science, Université de SherbrookeDepartment of Computer Science, Université de SherbrookeAbstract Background Horizontal gene transfer inference approaches are usually based on gene sequences: parametric methods search for patterns that deviate from a particular genomic signature, while phylogenetic methods use sequences to reconstruct the gene and species trees. However, it is well-known that sequences have difficulty identifying ancient transfers since mutations have enough time to erase all evidence of such events. In this work, we ask whether character-based methods can predict gene transfers. Their advantage over sequences is that homologous genes can have low DNA similarity, but still have retained enough important common motifs that allow them to have common character traits, for instance the same functional or expression profile. A phylogeny that has two separate clades that acquired the same character independently might indicate the presence of a transfer even in the absence of sequence similarity. Our contributions We introduce perfect transfer networks, which are phylogenetic networks that can explain the character diversity of a set of taxa under the assumption that characters have unique births, and that once a character is gained it is rarely lost. Examples of such traits include transposable elements, biochemical markers and emergence of organelles, just to name a few. We study the differences between our model and two similar models: perfect phylogenetic networks and ancestral recombination networks. Our goals are to initiate a study on the structural and algorithmic properties of perfect transfer networks. We then show that in polynomial time, one can decide whether a given network is a valid explanation for a set of taxa, and show how, for a given tree, one can add transfer edges to it so that it explains a set of taxa. We finally provide lower and upper bounds on the number of transfers required to explain a set of taxa, in the worst case.https://doi.org/10.1186/s13015-023-00242-2Horizontal gene transferTree-based networksPerfect phylogeniesCharacter-basedGene-expressionIndirect phylogenetic methods |
| spellingShingle | Alitzel López Sánchez Manuel Lafond Predicting horizontal gene transfers with perfect transfer networks Algorithms for Molecular Biology Horizontal gene transfer Tree-based networks Perfect phylogenies Character-based Gene-expression Indirect phylogenetic methods |
| title | Predicting horizontal gene transfers with perfect transfer networks |
| title_full | Predicting horizontal gene transfers with perfect transfer networks |
| title_fullStr | Predicting horizontal gene transfers with perfect transfer networks |
| title_full_unstemmed | Predicting horizontal gene transfers with perfect transfer networks |
| title_short | Predicting horizontal gene transfers with perfect transfer networks |
| title_sort | predicting horizontal gene transfers with perfect transfer networks |
| topic | Horizontal gene transfer Tree-based networks Perfect phylogenies Character-based Gene-expression Indirect phylogenetic methods |
| url | https://doi.org/10.1186/s13015-023-00242-2 |
| work_keys_str_mv | AT alitzellopezsanchez predictinghorizontalgenetransferswithperfecttransfernetworks AT manuellafond predictinghorizontalgenetransferswithperfecttransfernetworks |