Natural family-free genomic distance.

Rubert D, Martinez FV, Dias Vieira Braga M (2021)
Algorithms for molecular biology : AMB 16(1): 4.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA 2.84 MB
Abstract / Bemerkung
BACKGROUND: A classical problem in comparative genomics is to compute the rearrangement distance, that is the minimum number of large-scale rearrangements required to transform a given genome into another given genome. The traditional approaches in this area are family-based, i.e., require the classification of DNA fragments of both genomes into families. Furthermore, the most elementary family-based models, which are able to compute distances in polynomial time, restrict the families to occur at most once in each genome. In contrast, the distance computation in models that allow multifamilies (i.e., families with multiple occurrences) is NP-hard. Very recently, Bohnenkamper et al. (J Comput Biol 28:410-431, 2021) proposed an ILP formulation for computing the genomic distance of genomes with multifamilies, allowing structural rearrangements, represented by the generic double cut and join (DCJ) operation, and content-modifying insertions and deletions of DNA segments. This ILP is very efficient, but must maximize a matching of the genes in each multifamily, in order to prevent the free lunch artifact that would otherwise let empty or almost empty matchings give smaller distances.; RESULTS: In this paper, we adopt the alternative family-free setting that, instead of family classification, simply uses the pairwise similarities between DNA fragments of both genomes to compute their rearrangement distance. We adapted the ILP mentioned above and developed a model in which pairwise similarities are used to assign weights to both matched and unmatched genes, so that an optimal solution does not necessarily maximize the matching. Our model then results in a natural family-free genomic distance, that takes into consideration all given genes, without prior classification into families, and has a search space composed of matchings of any size. In spite of its bigger search space, our ILP seems to be boosted by a reduction of the number of co-optimal solutions due to the weights. Indeed, it converged faster than the original one by Bohnenkamper et al. for instances with the same number of multiple connections. We can handle not only bacterial genomes, but also fungi and insects, or sets of chromosomes of mammals and plants. In a comparison study of six fruit fly genomes, we obtained accurate results.
Stichworte
Comparative genomics; Genome rearrangement; DCJ-indel distance
Erscheinungsjahr
2021
Zeitschriftentitel
Algorithms for molecular biology : AMB
Band
16
Ausgabe
1
Art.-Nr.
4
eISSN
1748-7188
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2954832

Zitieren

Rubert D, Martinez FV, Dias Vieira Braga M. Natural family-free genomic distance. Algorithms for molecular biology : AMB. 2021;16(1): 4.
Rubert, D., Martinez, F. V., & Dias Vieira Braga, M. (2021). Natural family-free genomic distance. Algorithms for molecular biology : AMB, 16(1), 4. https://doi.org/10.1186/s13015-021-00183-8
Rubert, Diego, Martinez, Fabio V, and Dias Vieira Braga, Marília. 2021. “Natural family-free genomic distance.”. Algorithms for molecular biology : AMB 16 (1): 4.
Rubert, D., Martinez, F. V., and Dias Vieira Braga, M. (2021). Natural family-free genomic distance. Algorithms for molecular biology : AMB 16:4.
Rubert, D., Martinez, F.V., & Dias Vieira Braga, M., 2021. Natural family-free genomic distance. Algorithms for molecular biology : AMB, 16(1): 4.
D. Rubert, F.V. Martinez, and M. Dias Vieira Braga, “Natural family-free genomic distance.”, Algorithms for molecular biology : AMB, vol. 16, 2021, : 4.
Rubert, D., Martinez, F.V., Dias Vieira Braga, M.: Natural family-free genomic distance. Algorithms for molecular biology : AMB. 16, : 4 (2021).
Rubert, Diego, Martinez, Fabio V, and Dias Vieira Braga, Marília. “Natural family-free genomic distance.”. Algorithms for molecular biology : AMB 16.1 (2021): 4.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2022-01-18T12:49:13Z
MD5 Prüfsumme
0134b4f258b25abbee10935e70e77f5f


Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Quellen

PMID: 33971908
PubMed | Europe PMC

Suchen in

Google Scholar