Computing the family-free DCJ similarity
Rubert D, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FHV (2018)
BMC Bioinformatics 19(Suppl. 6): 152.
Zeitschriftenaufsatz
| Veröffentlicht | Englisch
Download
s12859-018-2130-5.stoye.pdf
1.62 MB
Autor*in
Rubert, DiegoUniBi 
;
Hoshino, Edna A.;
Dias Vieira Braga, MaríliaUniBi;
Stoye, JensUniBi ;
Martinez, Fábio Henrique ViduaniUniBi
;
Hoshino, Edna A.;
Dias Vieira Braga, MaríliaUniBi;
Stoye, JensUniBi ;
Martinez, Fábio Henrique ViduaniUniBiEinrichtung
Abstract / Bemerkung
Background
The genomic similarity is a large-scale measure for comparing two given genomes. In this work we study the (NP-hard) problem of computing the genomic similarity under the DCJ model in a setting that does not assume that the genes of the compared genomes are grouped into gene families. This problem is called family-free DCJ similarity.
Results
We propose an exact ILP algorithm to solve the family-free DCJ similarity problem, then we show its APX-hardness and present four combinatorial heuristics with computational experiments comparing their results to the ILP.
Conclusions
We show that the family-free DCJ similarity can be computed in reasonable time, although for larger genomes it is necessary to resort to heuristics. This provides a basis for further studies on the applicability and model refinement of family-free whole genome similarity measures.
Stichworte
Genome rearrangement;
Double-cut-and-join;
Family-free genomic similarity
Erscheinungsjahr
2018
Zeitschriftentitel
BMC Bioinformatics
Band
19
Ausgabe
Suppl. 6
Art.-Nr.
152
ISSN
1471-2105
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Deutsche Forschungsgemeinschaft und die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2919006
Zitieren
Rubert D, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FHV. Computing the family-free DCJ similarity. BMC Bioinformatics. 2018;19(Suppl. 6): 152.
Rubert, D., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., & Martinez, F. H. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6), 152. https://doi.org/10.1186/s12859-018-2130-5
Rubert, Diego, Hoshino, Edna A., Dias Vieira Braga, Marília, Stoye, Jens, and Martinez, Fábio Henrique Viduani. 2018. “Computing the family-free DCJ similarity”. BMC Bioinformatics 19 (Suppl. 6): 152.
Rubert, D., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., and Martinez, F. H. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics 19:152.
Rubert, D., et al., 2018. Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6): 152.
D. Rubert, et al., “Computing the family-free DCJ similarity”, BMC Bioinformatics, vol. 19, 2018, : 152.
Rubert, D., Hoshino, E.A., Dias Vieira Braga, M., Stoye, J., Martinez, F.H.V.: Computing the family-free DCJ similarity. BMC Bioinformatics. 19, : 152 (2018).
Rubert, Diego, Hoshino, Edna A., Dias Vieira Braga, Marília, Stoye, Jens, and Martinez, Fábio Henrique Viduani. “Computing the family-free DCJ similarity”. BMC Bioinformatics 19.Suppl. 6 (2018): 152.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Name
s12859-018-2130-5.stoye.pdf
1.62 MB
Access Level
Open Access
Zuletzt Hochgeladen
2019-09-06T09:18:58Z
MD5 Prüfsumme
e44aedab4664f12c505e2879fa252729
Daten bereitgestellt von European Bioinformatics Institute (EBI)
Zitationen in Europe PMC
Daten bereitgestellt von Europe PubMed Central.
30 References
Daten bereitgestellt von Europe PubMed Central.
AUTHOR UNKNOWN, 0
Genome rearrangements and sorting by reversals
Bafna V, Pevzner P., 1993
Bafna V, Pevzner P., 1993
Transforming men into mice (polynomial algorithm for genomic distance problem)
Hannenhalli S, Pevzner P., 1995
Hannenhalli S, Pevzner P., 1995
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
A unifying view of genome rearrangements
Bergeron A, Mixtacki J, Stoye J., 2006
Bergeron A, Mixtacki J, Stoye J., 2006
Double cut and join with insertions and deletions.
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
The complexity of calculating exemplar distances
Bryant D., 2000
Bryant D., 2000
Inapproximability of (1,2)-exemplar distance.
Bulteau L, Jiang M., IEEE/ACM Trans Comput Biol Bioinform 10(6), 2013
PMID: 24407297
Bulteau L, Jiang M., IEEE/ACM Trans Comput Biol Bioinform 10(6), 2013
PMID: 24407297
A pseudo-boolean framework for computing rearrangement distances between genomes with duplicates.
Angibaud S, Fertin G, Rusu I, Vialette S., J. Comput. Biol. 14(4), 2007
PMID: 17572018
Angibaud S, Fertin G, Rusu I, Vialette S., J. Comput. Biol. 14(4), 2007
PMID: 17572018
Efficient tools for computing the number of breakpoints and the number of adjacencies between two genomes with duplicate genes.
Angibaud S, Fertin G, Rusu I, Thevenin A, Vialette S., J. Comput. Biol. 15(8), 2008
PMID: 18774903
Angibaud S, Fertin G, Rusu I, Thevenin A, Vialette S., J. Comput. Biol. 15(8), 2008
PMID: 18774903
On the approximability of comparing genomes with duplicates
Angibaud S, Fertin G, Rusu I, Thévenin A, Vialette S., 2009
Angibaud S, Fertin G, Rusu I, Thévenin A, Vialette S., 2009
An exact algorithm to compute the DCJ distance for genomes with duplicate genes
Shao M, Lin Y, Moret B., 2014
Shao M, Lin Y, Moret B., 2014
Gene family assignment-free comparative genomics.
Doerr D, Thevenin A, Stoye J., BMC Bioinformatics 13 Suppl 19(), 2012
PMID: 23281826
Doerr D, Thevenin A, Stoye J., BMC Bioinformatics 13 Suppl 19(), 2012
PMID: 23281826
The potential of family-free genome comparison
Braga MDV, Chauve C, Doerr D, Jahn K, Stoye J, Thévenin A, Wittler R., 2013
Braga MDV, Chauve C, Doerr D, Jahn K, Stoye J, Thévenin A, Wittler R., 2013
Bayesian estimation of genomic distance.
Durrett R, Nielsen R, York TL., Genetics 166(1), 2004
PMID: 15020449
Durrett R, Nielsen R, York TL., Genetics 166(1), 2004
PMID: 15020449
On the family-free DCJ distance and similarity.
Martinez FV, Feijao P, Braga MD, Stoye J., Algorithms Mol Biol 10(), 2015
PMID: 25859276
Martinez FV, Feijao P, Braga MD, Stoye J., Algorithms Mol Biol 10(), 2015
PMID: 25859276
Algorithms for computing the family-free genomic similarity under DCJ
Rubert DP, Medeiros GL, Hoshino EA, Braga MDV, Stoye J, Martinez FV., 2017
Rubert DP, Medeiros GL, Hoshino EA, Braga MDV, Stoye J, Martinez FV., 2017
Non-breaking similarity of genomes with gene repetitions
Chen Z, Fu B, Xu J, Yang B, Zhao Z, Zhu B., 2007
Chen Z, Fu B, Xu J, Yang B, Zhao Z, Zhu B., 2007
Approximating the DCJ distance of balanced genomes in linear time.
Rubert DP, Feijao P, Braga MDV, Stoye J, Martinez FHV., Algorithms Mol Biol 12(), 2017
PMID: 28293275
Rubert DP, Feijao P, Braga MDV, Stoye J, Martinez FHV., Algorithms Mol Biol 12(), 2017
PMID: 28293275
Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion.
Shao M, Lin Y., BMC Bioinformatics 13(Suppl 19), 2012
PMID: PMC3527062
Shao M, Lin Y., BMC Bioinformatics 13(Suppl 19), 2012
PMID: PMC3527062
Algorithms for the assignment and transportation problems
Munkres J., 1957
Munkres J., 1957
Theoretical improvements in algorithmic efficiency for network flow problems
Edmonds J, Karp RM., 1972
Edmonds J, Karp RM., 1972
On some techniques useful for solution of transportation network problems
Tomizawa N., 1971
Tomizawa N., 1971
AUTHOR UNKNOWN, 0
Finding all the elementary circuits of a directed graph
Johnson D., 1975
Johnson D., 1975
A d/2 approximation for maximum weight independent set in d-claw free graphs
Berman P., 2000
Berman P., 2000
ALF--a simulation framework for genome evolution.
Dalquen DA, Anisimova M, Gonnet GH, Dessimoz C., Mol. Biol. Evol. 29(4), 2011
PMID: 22160766
Dalquen DA, Anisimova M, Gonnet GH, Dessimoz C., Mol. Biol. Evol. 29(4), 2011
PMID: 22160766
AUTHOR UNKNOWN, 0
Ohno S., 2013
Export
Markieren/ Markierung löschen
Markierte Publikationen
Web of Science
Dieser Datensatz im Web of Science®Quellen
PMID: 29745861
PubMed | Europe PMC
Suchen in
Google Scholar