Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes. Kececioglu, J. D. & Sankoff, D. In Proc. of Combinatorial Pattern Matching Symposium (CPM 1993), volume 684, of Lect Notes Comput Sci, pages 87–105, London, UK, 1993. Springer, Berlin. abstract bibtex Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements and reverses their order. For this problem we develop two algorithms: a greedy approximation algorithm that finds a solution provably close to optimal in O(n2) time and O(n) space for an n element permutation, and a branch and bound exact algorithm that finds an optimal solution in O(mL(n, n)) time and O(n 2) space, where m is the size of the branch and bound search tree and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum, and guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch and bound algorithm are a novel application of maximum weight matchings, shortest paths, and linear programming. In a series of experiments we study the performance of an implementation. For random permutations we find that the average difference between the upper and lower bounds is less than 3 reversals for nle50. Due to the tightness of these bounds we can solve to optimality random permutations on 30 elements in a few minutes of computer time.
@InProceedings{kececioglu93exact,
author = {John D. Kececioglu and David Sankoff},
title = {Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes},
booktitle = {Proc. of Combinatorial Pattern Matching Symposium (CPM 1993)},
year = {1993},
volume = {684},
series = lncs,
pages = {87--105},
address = {London, UK},
publisher = Springer,
abstract = {Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements and reverses their order. For this problem we develop two algorithms: a greedy approximation algorithm that finds a solution provably close to optimal in O(n2) time and O(n) space for an n element permutation, and a branch and bound exact algorithm that finds an optimal solution in O(mL(n, n)) time and O(n 2) space, where m is the size of the branch and bound search tree and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum, and guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch and bound algorithm are a novel application of maximum weight matchings, shortest paths, and linear programming. In a series of experiments we study the performance of an implementation. For random permutations we find that the average difference between the upper and lower bounds is less than 3 reversals for nle50. Due to the tightness of these bounds we can solve to optimality random permutations on 30 elements in a few minutes of computer time.},
file = {KececiogluSankoff_ExactApproximationAlgorithmsSBR_CPM_1993.pdf:1993/KececiogluSankoff_ExactApproximationAlgorithmsSBR_CPM_1993.pdf:PDF},
isbn = {3-540-56764-X},
}
Downloads: 0
{"_id":"QxHgvGuP2Bw6Dx5hw","bibbaseid":"kececioglu-sankoff-exactandapproximationalgorithmsfortheinversiondistancebetweentwochromosomes-1993","authorIDs":[],"author_short":["Kececioglu, J. D.","Sankoff, D."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["John","D."],"propositions":[],"lastnames":["Kececioglu"],"suffixes":[]},{"firstnames":["David"],"propositions":[],"lastnames":["Sankoff"],"suffixes":[]}],"title":"Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes","booktitle":"Proc. of Combinatorial Pattern Matching Symposium (CPM 1993)","year":"1993","volume":"684","series":"Lect Notes Comput Sci","pages":"87–105","address":"London, UK","publisher":"Springer, Berlin","abstract":"Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements and reverses their order. For this problem we develop two algorithms: a greedy approximation algorithm that finds a solution provably close to optimal in O(n2) time and O(n) space for an n element permutation, and a branch and bound exact algorithm that finds an optimal solution in O(mL(n, n)) time and O(n 2) space, where m is the size of the branch and bound search tree and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum, and guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch and bound algorithm are a novel application of maximum weight matchings, shortest paths, and linear programming. In a series of experiments we study the performance of an implementation. For random permutations we find that the average difference between the upper and lower bounds is less than 3 reversals for nle50. Due to the tightness of these bounds we can solve to optimality random permutations on 30 elements in a few minutes of computer time.","file":"KececiogluSankoff_ExactApproximationAlgorithmsSBR_CPM_1993.pdf:1993/KececiogluSankoff_ExactApproximationAlgorithmsSBR_CPM_1993.pdf:PDF","isbn":"3-540-56764-X","bibtex":"@InProceedings{kececioglu93exact,\n author = {John D. Kececioglu and David Sankoff},\n title = {Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes},\n booktitle = {Proc. of Combinatorial Pattern Matching Symposium (CPM 1993)},\n year = {1993},\n volume = {684},\n series = lncs,\n pages = {87--105},\n address = {London, UK},\n publisher = Springer,\n abstract = {Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements and reverses their order. For this problem we develop two algorithms: a greedy approximation algorithm that finds a solution provably close to optimal in O(n2) time and O(n) space for an n element permutation, and a branch and bound exact algorithm that finds an optimal solution in O(mL(n, n)) time and O(n 2) space, where m is the size of the branch and bound search tree and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum, and guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch and bound algorithm are a novel application of maximum weight matchings, shortest paths, and linear programming. In a series of experiments we study the performance of an implementation. For random permutations we find that the average difference between the upper and lower bounds is less than 3 reversals for nle50. Due to the tightness of these bounds we can solve to optimality random permutations on 30 elements in a few minutes of computer time.},\n file = {KececiogluSankoff_ExactApproximationAlgorithmsSBR_CPM_1993.pdf:1993/KececiogluSankoff_ExactApproximationAlgorithmsSBR_CPM_1993.pdf:PDF},\n isbn = {3-540-56764-X},\n}\n\n","author_short":["Kececioglu, J. D.","Sankoff, D."],"key":"kececioglu93exact","id":"kececioglu93exact","bibbaseid":"kececioglu-sankoff-exactandapproximationalgorithmsfortheinversiondistancebetweentwochromosomes-1993","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.204Z","downloads":0,"keywords":[],"search_terms":["exact","approximation","algorithms","inversion","distance","between","two","chromosomes","kececioglu","sankoff"],"title":"Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes","year":1993,"dataSources":["C5FtkvWWggFfMJTFX"]}