---
_id: '44857'
abstract:
- lang: eng
  text: Ancestral reconstruction is a classic task in comparative genomics. Here,
    we study the genome median problem, a related computational problem which, given
    a set of three or more genomes, asks to find a new genome that minimizes the sum
    of pairwise distances between it and the given genomes. The distance stands for
    the amount of evolution observed at the genome level, for which we determine the
    minimum number of rearrangement operations necessary to transform one genome into
    the other. For almost all rearrangement operations the median problem is NP-hard,
    with the exception of the breakpoint median that can be constructed efficiently
    for multichromosomal circular and mixed genomes. In this work, we study the median
    problem under a restricted rearrangement measure called c4-distance, which is
    closely related to the breakpoint and the DCJ distance. We identify tight bounds
    and decomposers of the c4-median and develop algorithms for its construction,
    one exact ILP-based and three combinatorial heuristics. Subsequently, we perform
    experiments on simulated data sets. Our results suggest that the c4-distance is
    useful for the study the genome median problem, from theoretical and practical
    perspectives.
author:
- first_name: Helmuth O.M.
  full_name: Silva, Helmuth O.M.
  last_name: Silva
- first_name: Diego P.
  full_name: Rubert, Diego P.
  last_name: Rubert
- first_name: Eloi
  full_name: Araujo, Eloi
  last_name: Araujo
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
- first_name: Daniel
  full_name: Doerr, Daniel
  last_name: Doerr
- first_name: Fábio V.
  full_name: Martinez, Fábio V.
  last_name: Martinez
citation:
  ama: Silva HOM, Rubert DP, Araujo E, Steffen E, Doerr D, Martinez FV. Algorithms
    for the genome median under a restricted measure of rearrangement. <i>RAIRO -
    Operations Research</i>. 2023;57(3):1045-1058. doi:<a href="https://doi.org/10.1051/ro/2023052">10.1051/ro/2023052</a>
  apa: Silva, H. O. M., Rubert, D. P., Araujo, E., Steffen, E., Doerr, D., &#38; Martinez,
    F. V. (2023). Algorithms for the genome median under a restricted measure of rearrangement.
    <i>RAIRO - Operations Research</i>, <i>57</i>(3), 1045–1058. <a href="https://doi.org/10.1051/ro/2023052">https://doi.org/10.1051/ro/2023052</a>
  bibtex: '@article{Silva_Rubert_Araujo_Steffen_Doerr_Martinez_2023, title={Algorithms
    for the genome median under a restricted measure of rearrangement}, volume={57},
    DOI={<a href="https://doi.org/10.1051/ro/2023052">10.1051/ro/2023052</a>}, number={3},
    journal={RAIRO - Operations Research}, publisher={EDP Sciences}, author={Silva,
    Helmuth O.M. and Rubert, Diego P. and Araujo, Eloi and Steffen, Eckhard and Doerr,
    Daniel and Martinez, Fábio V.}, year={2023}, pages={1045–1058} }'
  chicago: 'Silva, Helmuth O.M., Diego P. Rubert, Eloi Araujo, Eckhard Steffen, Daniel
    Doerr, and Fábio V. Martinez. “Algorithms for the Genome Median under a Restricted
    Measure of Rearrangement.” <i>RAIRO - Operations Research</i> 57, no. 3 (2023):
    1045–58. <a href="https://doi.org/10.1051/ro/2023052">https://doi.org/10.1051/ro/2023052</a>.'
  ieee: 'H. O. M. Silva, D. P. Rubert, E. Araujo, E. Steffen, D. Doerr, and F. V.
    Martinez, “Algorithms for the genome median under a restricted measure of rearrangement,”
    <i>RAIRO - Operations Research</i>, vol. 57, no. 3, pp. 1045–1058, 2023, doi:
    <a href="https://doi.org/10.1051/ro/2023052">10.1051/ro/2023052</a>.'
  mla: Silva, Helmuth O. M., et al. “Algorithms for the Genome Median under a Restricted
    Measure of Rearrangement.” <i>RAIRO - Operations Research</i>, vol. 57, no. 3,
    EDP Sciences, 2023, pp. 1045–58, doi:<a href="https://doi.org/10.1051/ro/2023052">10.1051/ro/2023052</a>.
  short: H.O.M. Silva, D.P. Rubert, E. Araujo, E. Steffen, D. Doerr, F.V. Martinez,
    RAIRO - Operations Research 57 (2023) 1045–1058.
date_created: 2023-05-16T08:48:22Z
date_updated: 2023-05-16T08:49:30Z
department:
- _id: '542'
doi: 10.1051/ro/2023052
intvolume: '        57'
issue: '3'
keyword:
- Management Science and Operations Research
- Computer Science Applications
- Theoretical Computer Science
language:
- iso: eng
page: 1045-1058
publication: RAIRO - Operations Research
publication_identifier:
  issn:
  - 0399-0559
  - 2804-7303
publication_status: published
publisher: EDP Sciences
status: public
title: Algorithms for the genome median under a restricted measure of rearrangement
type: journal_article
user_id: '15540'
volume: 57
year: '2023'
...
---
_id: '53879'
author:
- first_name: Sajad
  full_name: Kazemi, Sajad
  last_name: Kazemi
- first_name: Madjid
  full_name: Tavana, Madjid
  id: '31858'
  last_name: Tavana
- first_name: Mehdi
  full_name: Toloo, Mehdi
  last_name: Toloo
- first_name: Nikolay A.
  full_name: Zenkevich, Nikolay A.
  last_name: Zenkevich
citation:
  ama: Kazemi S, Tavana M, Toloo M, Zenkevich NA. A common weights model for investigating
    efficiency-based leadership in the russian banking industry. <i>RAIRO - Operations
    Research</i>. 2021;55(1):213-229. doi:<a href="https://doi.org/10.1051/ro/2020143">10.1051/ro/2020143</a>
  apa: Kazemi, S., Tavana, M., Toloo, M., &#38; Zenkevich, N. A. (2021). A common
    weights model for investigating efficiency-based leadership in the russian banking
    industry. <i>RAIRO - Operations Research</i>, <i>55</i>(1), 213–229. <a href="https://doi.org/10.1051/ro/2020143">https://doi.org/10.1051/ro/2020143</a>
  bibtex: '@article{Kazemi_Tavana_Toloo_Zenkevich_2021, title={A common weights model
    for investigating efficiency-based leadership in the russian banking industry},
    volume={55}, DOI={<a href="https://doi.org/10.1051/ro/2020143">10.1051/ro/2020143</a>},
    number={1}, journal={RAIRO - Operations Research}, publisher={EDP Sciences}, author={Kazemi,
    Sajad and Tavana, Madjid and Toloo, Mehdi and Zenkevich, Nikolay A.}, year={2021},
    pages={213–229} }'
  chicago: 'Kazemi, Sajad, Madjid Tavana, Mehdi Toloo, and Nikolay A. Zenkevich. “A
    Common Weights Model for Investigating Efficiency-Based Leadership in the Russian
    Banking Industry.” <i>RAIRO - Operations Research</i> 55, no. 1 (2021): 213–29.
    <a href="https://doi.org/10.1051/ro/2020143">https://doi.org/10.1051/ro/2020143</a>.'
  ieee: 'S. Kazemi, M. Tavana, M. Toloo, and N. A. Zenkevich, “A common weights model
    for investigating efficiency-based leadership in the russian banking industry,”
    <i>RAIRO - Operations Research</i>, vol. 55, no. 1, pp. 213–229, 2021, doi: <a
    href="https://doi.org/10.1051/ro/2020143">10.1051/ro/2020143</a>.'
  mla: Kazemi, Sajad, et al. “A Common Weights Model for Investigating Efficiency-Based
    Leadership in the Russian Banking Industry.” <i>RAIRO - Operations Research</i>,
    vol. 55, no. 1, EDP Sciences, 2021, pp. 213–29, doi:<a href="https://doi.org/10.1051/ro/2020143">10.1051/ro/2020143</a>.
  short: S. Kazemi, M. Tavana, M. Toloo, N.A. Zenkevich, RAIRO - Operations Research
    55 (2021) 213–229.
date_created: 2024-05-04T14:45:40Z
date_updated: 2024-05-04T15:13:07Z
department:
- _id: '277'
doi: 10.1051/ro/2020143
intvolume: '        55'
issue: '1'
language:
- iso: eng
page: 213-229
publication: RAIRO - Operations Research
publication_identifier:
  issn:
  - 0399-0559
  - 1290-3868
publication_status: published
publisher: EDP Sciences
status: public
title: A common weights model for investigating efficiency-based leadership in the
  russian banking industry
type: journal_article
user_id: '51811'
volume: 55
year: '2021'
...
---
_id: '54010'
author:
- first_name: Rashed Khanjani
  full_name: Shiraz, Rashed Khanjani
  last_name: Shiraz
- first_name: Madjid
  full_name: Tavana, Madjid
  id: '31858'
  last_name: Tavana
- first_name: Debora
  full_name: Di Caprio, Debora
  last_name: Di Caprio
citation:
  ama: Shiraz RK, Tavana M, Di Caprio D. Chance-constrained data envelopment analysis
    modeling with random-rough data. <i>RAIRO - Operations Research</i>. 2018;52(1):259-284.
    doi:<a href="https://doi.org/10.1051/ro/2016076">10.1051/ro/2016076</a>
  apa: Shiraz, R. K., Tavana, M., &#38; Di Caprio, D. (2018). Chance-constrained data
    envelopment analysis modeling with random-rough data. <i>RAIRO - Operations Research</i>,
    <i>52</i>(1), 259–284. <a href="https://doi.org/10.1051/ro/2016076">https://doi.org/10.1051/ro/2016076</a>
  bibtex: '@article{Shiraz_Tavana_Di Caprio_2018, title={Chance-constrained data envelopment
    analysis modeling with random-rough data}, volume={52}, DOI={<a href="https://doi.org/10.1051/ro/2016076">10.1051/ro/2016076</a>},
    number={1}, journal={RAIRO - Operations Research}, publisher={EDP Sciences}, author={Shiraz,
    Rashed Khanjani and Tavana, Madjid and Di Caprio, Debora}, year={2018}, pages={259–284}
    }'
  chicago: 'Shiraz, Rashed Khanjani, Madjid Tavana, and Debora Di Caprio. “Chance-Constrained
    Data Envelopment Analysis Modeling with Random-Rough Data.” <i>RAIRO - Operations
    Research</i> 52, no. 1 (2018): 259–84. <a href="https://doi.org/10.1051/ro/2016076">https://doi.org/10.1051/ro/2016076</a>.'
  ieee: 'R. K. Shiraz, M. Tavana, and D. Di Caprio, “Chance-constrained data envelopment
    analysis modeling with random-rough data,” <i>RAIRO - Operations Research</i>,
    vol. 52, no. 1, pp. 259–284, 2018, doi: <a href="https://doi.org/10.1051/ro/2016076">10.1051/ro/2016076</a>.'
  mla: Shiraz, Rashed Khanjani, et al. “Chance-Constrained Data Envelopment Analysis
    Modeling with Random-Rough Data.” <i>RAIRO - Operations Research</i>, vol. 52,
    no. 1, EDP Sciences, 2018, pp. 259–84, doi:<a href="https://doi.org/10.1051/ro/2016076">10.1051/ro/2016076</a>.
  short: R.K. Shiraz, M. Tavana, D. Di Caprio, RAIRO - Operations Research 52 (2018)
    259–284.
date_created: 2024-05-06T16:56:36Z
date_updated: 2024-05-06T16:58:31Z
department:
- _id: '277'
doi: 10.1051/ro/2016076
intvolume: '        52'
issue: '1'
language:
- iso: eng
page: 259-284
publication: RAIRO - Operations Research
publication_identifier:
  issn:
  - 0399-0559
  - 1290-3868
publication_status: published
publisher: EDP Sciences
status: public
title: Chance-constrained data envelopment analysis modeling with random-rough data
type: journal_article
user_id: '51811'
volume: 52
year: '2018'
...