The Reversal Median Problem

References

• Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M.Combinatorial Optimization Problems and Their Approximability Properties (1999) (Springer-Verlag, Berlin, Germany) Google Scholar
• Bader D. A., Moret B. M. E., Yan M. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology (2001) 8:483–491Crossref, Google Scholar
• Bafna V., Pevzner P. A. Genome rearrangements and sorting by reversals. SIAM Journal on Computing (1996) 25:272–289Crossref, Google Scholar
• Berman P., Karpinski M. On some tighter inapproximability results: Further improvements. Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science (2000) (Springer Verlag, Berlin, Germany) 200–209No. 1644Google Scholar
• Blanchette M., Bourque G., Sankoff D., Miyano S., Takagi T. Breakpoint phylogenies. Proceedings of Genome Informatics 1997 (1997) (Universal Academy Press, Tokyo, Japan) 25–34Google Scholar
• Blanchette M. (1999) . Personal communicationGoogle Scholar
• Bourque G., Pevzner P. A. Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Research (2002) . ForthcomingGoogle Scholar
• Bryant D. A lower bound for the breakpoint bhylogeny problem. Journal of Discrete Algorithms (2002) . ForthcomingGoogle Scholar
• Caprara A. Sorting permutations by reversals and Eulerian cycle decompositions. SIAM Journal on Discrete Mathematics (1999a) 12:91–110Crossref, Google Scholar
• Caprara A. On the tightness of the alternating-cycle lower bound for sorting by reversals. Journal of Combinatorial Optimization (1999b) 3:149–182Crossref, Google Scholar
• Caprara A. Formulations and hardness of multiple sorting by reversals. Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB'99) (1999c) (ACM Press, New York) 84–93Crossref, Google Scholar
• Caprara A. The reversal median problem. Research Report OR/01/12 (2001) . DEIS, University of Bologna, Italy http://www.or.deis.unibo.it/alberto/online.htmGoogle Scholar
• Caprara A., Lancia G., Ng S. K. Sorting permutations by reversals through branch-and-price. INFORMS Journal on Computing (2001) 13:224–244Link, Google Scholar
• Christie D. A. A 3/2 approximation algorithm for sorting by reversals. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998) (ACM Press, New York) 244–252Google Scholar
• Cosner M. E., Jansen R. K., Moret B. M. E., Rauberson L. A., Wang L-S., Warnow T., Wyman S., Sankoff D., Nadeau J. H. An empirical comparison of phylogenetic methods on chloroplast gene order data in campanulaceae. Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 99–121Crossref, Google Scholar
• Grötschel M., Lovčsz L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica (1981) 1:169–197Crossref, Google Scholar
• Gusfield D.Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology (1997) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Hannenhalli S., Chappey C., Koonin E. V., Pevzner P. A. Genome sequence comparison and scenarios for gene rearrangements: A test case. Genomics (1995) 30:299–311Crossref, Google Scholar
• Hannenhalli S., Pevzner P. A. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). Journal of the ACM (1999) 48:1–27Crossref, Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M., Magnanti T., Monma C., Nemhauser G. The traveling salesman problem. Network Models, Handbooks in Operations Research and Management Science (1995) 7(Elsevier, Amsterdam, The Netherlands) 225–330Google Scholar
• Kaplan H., Shamir R., Tarjan R. E. Faster and simpler algorithm for sorting signed permutations by reversals. SIAM Journal on Computing (2000) 29:880–892Crossref, Google Scholar
• Kececioglu J., Sankoff D. Efficient bounds for oriented chromosome inversion distance. Proceedings of 5th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science (1994) (Springer Verlag, Berlin, Germany) 307–325No. 807Crossref, Google Scholar
• Kececioglu J., Sankoff D. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica (1995) 13:180–210Crossref, Google Scholar
• Moret B. M. E., Tang J., Wang L-S., Warnow T. Steps toward accurate reconstructions of phylogenies from gene-order data. Journal of Computer and System Sciences (2002) 65(3):508–525Crossref, Google Scholar
• Moret B. M. E., Wang L-S., Warnow T., Wyman S. K. New approaches to phylogeny reconstruction from gene order data. Bioinformatics (2001a) 17:165S–173SCrossref, Google Scholar
• Moret B. M. E., Wyman S. K., Bader D. A., Warnow T., Yan M. A new implementation and detailed study of breakpoint analysis. Proceedings of the 6th Pacific Symposium on Biocomputing (PSB 2001) (2001b) (World Scientific Publishing, Singapore) 583–594Google Scholar
• Pe'er I., Shamir R. The median problems for break points are NP-complete. (1998) . ECCC Report No. 71, University of Trier, Germany. http://www.eccc.uni-trier.deGoogle Scholar
• Pe'er I., Shamir R., Sankoff D., Nadeau J. H. Approximation algorithms for the median problem in the breakpoint model. Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 225–241Crossref, Google Scholar
• Sankoff D., Blanchette M. Multiple genome rearrangement and breakpoint phylogenies. Journal of Computational Biology (2000) 5:555–570Crossref, Google Scholar
• Sankoff D., Bryant D., Denault M., Lang B. F., Burger G. Early eukaryote evolution based on mitochondrial gene order breakpoints. Journal of Computational Biology (2000) 7:521–536Crossref, Google Scholar
• Sankoff D., El-Mabrouk N., Sankoff D., Nadeau J. H. Duplication, rearrangement and reconciliation. Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 537–550Crossref, Google Scholar
• Sankoff D., Nadeau J. H.Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) Crossref, Google Scholar
• Sankoff D., Sundaram G., Kececioglu J. Steiner points in the space of genome rearrangements. International Journal of Foundations of Computer Science (1996) 7:1–9Crossref, Google Scholar
• Setubal J., Meidanis J.Introduction to Computational Molecular Biology (1997) (PWS Publishing, Boston, MA) Google Scholar