Algorithms for a Restricted Genome Median Problem
Silva HOM, Rubert D, Araujo E, Martinez FV (2022)
In: Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting . Bezerra Campêlo Neto M, Gomes Fernandes C, Fernandes dos Santos V (Eds); Porto Alegre, RS: Sociedade Brasileira de Computação - SBC: 45-48.
Kurzbeitrag Konferenz / Poster
| Veröffentlicht | Englisch
Download
Autor*in
Silva, Helmuth O. M.;
Rubert, DiegoUniBi 
;
Araujo, Eloi;
Martinez, Fábio V.
;
Araujo, Eloi;
Martinez, Fábio V.Herausgeber*in
Bezerra Campêlo Neto, Manoel;
Gomes Fernandes, Cristina;
Fernandes dos Santos, Vinicius
Einrichtung
Abstract / Bemerkung
In the median problem we are given a set of three or more genomes and want to find a new genome minimizing the sum of pairwise distances between it and the given genomes. For almost all rearrangement operations the median problem is NP-hard. We study the median problem under a restricted rearrangement measure called c4-distance, which is closely related to breakpoint and DCJ distances. We propose two algorithms for its construction, one exact ILP-based and a combinatorial heuristic, and perform experiments on simulated data.
Erscheinungsjahr
2022
Titel des Konferenzbandes
Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting
Seite(n)
45-48
Urheberrecht / Lizenzen
Konferenz
VII Encontro de Teoria da Computação
Konferenzort
Niterói, RJ, Brazil
Konferenzdatum
2022-07-31 – 2022-08-05
ISSN
2595-6116
Page URI
https://pub.uni-bielefeld.de/record/2965058
Zitieren
Silva HOM, Rubert D, Araujo E, Martinez FV. Algorithms for a Restricted Genome Median Problem. In: Bezerra Campêlo Neto M, Gomes Fernandes C, Fernandes dos Santos V, eds. Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting . Porto Alegre, RS: Sociedade Brasileira de Computação - SBC; 2022: 45-48.
Silva, H. O. M., Rubert, D., Araujo, E., & Martinez, F. V. (2022). Algorithms for a Restricted Genome Median Problem. In M. Bezerra Campêlo Neto, C. Gomes Fernandes, & V. Fernandes dos Santos (Eds.), Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting (pp. 45-48). Porto Alegre, RS: Sociedade Brasileira de Computação - SBC. https://doi.org/10.5753/etc.2022.222734
Silva, Helmuth O. M., Rubert, Diego, Araujo, Eloi, and Martinez, Fábio V. 2022. “Algorithms for a Restricted Genome Median Problem”. In Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting , ed. Manoel Bezerra Campêlo Neto, Cristina Gomes Fernandes, and Vinicius Fernandes dos Santos, 45-48. Porto Alegre, RS: Sociedade Brasileira de Computação - SBC.
Silva, H. O. M., Rubert, D., Araujo, E., and Martinez, F. V. (2022). “Algorithms for a Restricted Genome Median Problem” in Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting , Bezerra Campêlo Neto, M., Gomes Fernandes, C., and Fernandes dos Santos, V. eds. (Porto Alegre, RS: Sociedade Brasileira de Computação - SBC), 45-48.
Silva, H.O.M., et al., 2022. Algorithms for a Restricted Genome Median Problem. In M. Bezerra Campêlo Neto, C. Gomes Fernandes, & V. Fernandes dos Santos, eds. Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting . Porto Alegre, RS: Sociedade Brasileira de Computação - SBC, pp. 45-48.
H.O.M. Silva, et al., “Algorithms for a Restricted Genome Median Problem”, Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting , M. Bezerra Campêlo Neto, C. Gomes Fernandes, and V. Fernandes dos Santos, eds., Porto Alegre, RS: Sociedade Brasileira de Computação - SBC, 2022, pp.45-48.
Silva, H.O.M., Rubert, D., Araujo, E., Martinez, F.V.: Algorithms for a Restricted Genome Median Problem. In: Bezerra Campêlo Neto, M., Gomes Fernandes, C., and Fernandes dos Santos, V. (eds.) Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting . p. 45-48. Sociedade Brasileira de Computação - SBC, Porto Alegre, RS (2022).
Silva, Helmuth O. M., Rubert, Diego, Araujo, Eloi, and Martinez, Fábio V. “Algorithms for a Restricted Genome Median Problem”. Anais do VII Encontro de Teoria da Computação (ETC 2022) = Proceedings of the 7th Theory of Computation Meeting . Ed. Manoel Bezerra Campêlo Neto, Cristina Gomes Fernandes, and Vinicius Fernandes dos Santos. Porto Alegre, RS: Sociedade Brasileira de Computação - SBC, 2022. 45-48.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Name
Access Level
Open Access
Zuletzt Hochgeladen
2022-08-12T09:13:17Z
MD5 Prüfsumme
0e78602b8d19c47c37297dfebe7dc582
Link(s) zu Volltext(en)
Access Level
Open Access
Google Scholar