Two notes on genome rearrangement. Ozery-Flato, M. & Shamir, R. J Bioinform Comput Biol, 1(1):71–94, 2003. abstract bibtex A central problem in genome rearrangement is finding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed genome by reversals and translocations (SBRT). Hannenhalli and Pevzner presented a duality theorem for SBRT which leads to a polynomial time algorithm for sorting a multi-chromosomal genome using a minimum number of reversals and translocations. However, there is one case for which their theorem and algorithm fail. We describe that case and suggest a correction to the theorem and the polynomial algorithm. The solution of SBRT uses a reduction to the problem of sorting a signed permutation by reversals (SBR). The best extant algorithms for SBR require quadratic time. The common approach to solve SBR is by finding a safe reversal using the overlap graph or the interleaving graph of a permutation. We describe a family of signed permutations which proves a quadratic lower bound on the number of affected vertices in the overlap/interleaving graph during any optimal sorting scenario. This implies, in particular, an Omega(n3) lower bound for Bergeron's algorithm.
@Article{ozery-flato03two,
author = {Michal Ozery-Flato and Ron Shamir},
title = {Two notes on genome rearrangement.},
journal = {J Bioinform Comput Biol},
year = {2003},
volume = {1},
number = {1},
pages = {71--94},
abstract = {A central problem in genome rearrangement is finding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed genome by reversals and translocations (SBRT). Hannenhalli and Pevzner presented a duality theorem for SBRT which leads to a polynomial time algorithm for sorting a multi-chromosomal genome using a minimum number of reversals and translocations. However, there is one case for which their theorem and algorithm fail. We describe that case and suggest a correction to the theorem and the polynomial algorithm. The solution of SBRT uses a reduction to the problem of sorting a signed permutation by reversals (SBR). The best extant algorithms for SBR require quadratic time. The common approach to solve SBR is by finding a safe reversal using the overlap graph or the interleaving graph of a permutation. We describe a family of signed permutations which proves a quadratic lower bound on the number of affected vertices in the overlap/interleaving graph during any optimal sorting scenario. This implies, in particular, an Omega(n3) lower bound for Bergeron's algorithm.},
file = {Ozery-FlatoShamir_TwoNotesGenomeRearrangement_JBioinformComputBiol_2003.pdf:2003/Ozery-FlatoShamir_TwoNotesGenomeRearrangement_JBioinformComputBiol_2003.pdf:PDF},
keywords = {Gene Rearrangement; Genomics; Translocation, Genetic},
optmonth = apr,
owner = {truss},
pmid = {15290782},
timestamp = {2006.12.20},
}
Downloads: 0
{"_id":"RpP4b9LSDN7X2KSEL","bibbaseid":"ozeryflato-shamir-twonotesongenomerearrangement-2003","authorIDs":[],"author_short":["Ozery-Flato, M.","Shamir, R."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Michal"],"propositions":[],"lastnames":["Ozery-Flato"],"suffixes":[]},{"firstnames":["Ron"],"propositions":[],"lastnames":["Shamir"],"suffixes":[]}],"title":"Two notes on genome rearrangement.","journal":"J Bioinform Comput Biol","year":"2003","volume":"1","number":"1","pages":"71–94","abstract":"A central problem in genome rearrangement is finding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed genome by reversals and translocations (SBRT). Hannenhalli and Pevzner presented a duality theorem for SBRT which leads to a polynomial time algorithm for sorting a multi-chromosomal genome using a minimum number of reversals and translocations. However, there is one case for which their theorem and algorithm fail. We describe that case and suggest a correction to the theorem and the polynomial algorithm. The solution of SBRT uses a reduction to the problem of sorting a signed permutation by reversals (SBR). The best extant algorithms for SBR require quadratic time. The common approach to solve SBR is by finding a safe reversal using the overlap graph or the interleaving graph of a permutation. We describe a family of signed permutations which proves a quadratic lower bound on the number of affected vertices in the overlap/interleaving graph during any optimal sorting scenario. This implies, in particular, an Omega(n3) lower bound for Bergeron's algorithm.","file":"Ozery-FlatoShamir_TwoNotesGenomeRearrangement_JBioinformComputBiol_2003.pdf:2003/Ozery-FlatoShamir_TwoNotesGenomeRearrangement_JBioinformComputBiol_2003.pdf:PDF","keywords":"Gene Rearrangement; Genomics; Translocation, Genetic","optmonth":"April","owner":"truss","pmid":"15290782","timestamp":"2006.12.20","bibtex":"@Article{ozery-flato03two,\n author = {Michal Ozery-Flato and Ron Shamir},\n title = {Two notes on genome rearrangement.},\n journal = {J Bioinform Comput Biol},\n year = {2003},\n volume = {1},\n number = {1},\n pages = {71--94},\n abstract = {A central problem in genome rearrangement is finding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed genome by reversals and translocations (SBRT). Hannenhalli and Pevzner presented a duality theorem for SBRT which leads to a polynomial time algorithm for sorting a multi-chromosomal genome using a minimum number of reversals and translocations. However, there is one case for which their theorem and algorithm fail. We describe that case and suggest a correction to the theorem and the polynomial algorithm. The solution of SBRT uses a reduction to the problem of sorting a signed permutation by reversals (SBR). The best extant algorithms for SBR require quadratic time. The common approach to solve SBR is by finding a safe reversal using the overlap graph or the interleaving graph of a permutation. We describe a family of signed permutations which proves a quadratic lower bound on the number of affected vertices in the overlap/interleaving graph during any optimal sorting scenario. This implies, in particular, an Omega(n3) lower bound for Bergeron's algorithm.},\n file = {Ozery-FlatoShamir_TwoNotesGenomeRearrangement_JBioinformComputBiol_2003.pdf:2003/Ozery-FlatoShamir_TwoNotesGenomeRearrangement_JBioinformComputBiol_2003.pdf:PDF},\n keywords = {Gene Rearrangement; Genomics; Translocation, Genetic},\n optmonth = apr,\n owner = {truss},\n pmid = {15290782},\n timestamp = {2006.12.20},\n}\n\n","author_short":["Ozery-Flato, M.","Shamir, R."],"key":"ozery-flato03two","id":"ozery-flato03two","bibbaseid":"ozeryflato-shamir-twonotesongenomerearrangement-2003","role":"author","urls":{},"keyword":["Gene Rearrangement; Genomics; Translocation","Genetic"],"downloads":0},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.478Z","downloads":0,"keywords":["gene rearrangement; genomics; translocation","genetic"],"search_terms":["two","notes","genome","rearrangement","ozery-flato","shamir"],"title":"Two notes on genome rearrangement.","year":2003,"dataSources":["C5FtkvWWggFfMJTFX"]}