This page is for archival use only. Please use the publications page at EPFL, my new institution.

TEXTBOOKS

• Moret, B.M.E.
  The Theory of Computation. Addison-Wesley, Reading, Mass., 1998. A comprehensive set of worked solutions, additional exercises, solution manual, comments, and the usual errata are available at the home site for the text.
• Moret, B.M.E., and Shapiro, H.D.
  Algorithms from P to NP, Volume I: Design and Efficiency. Benjamin-Cummings Publishing Co., Menlo Park, CA, 1991 (576+xvi pp.).
  All of the programs in the text, as well as a list of errata, are available through anonymous ftp from ftp.cs.unm.edu.

EDITED VOLUMES

• Bücher, P., and Moret, B.M.E., eds.
  Proceedings of the Sixth Annual Workshop on Algorithms in Bioinformatics (WABI'06), Lecture Notes in Computer Science 4175, Springer Verlag, 2006 (410pp.)
• Fleischer, R., Moret, B.M.E., and Schmidt, E.M., eds.
  Experimental Algorithmics, Lecture Notes in Computer Science 2547, Springer Verlag, 2002 (296pp.)
• Gascuel, O., and Moret, B.M.E., eds.
  Proceedings of the First Annual Workshop on Algorithms in Bioinformatics (WABI'01), Lecture Notes in Computer Science 2149, Springer Verlag, 2001 (310pp.)
• Moret, B.M.E., guest ed.
  Tenth Annual ACM-SIAM Symposium on Discrete Algorithms SODA'99 in Journal of Algorithms 38, 1 (2001), 333pp.
• Goldberg, A., and Moret, B.M.E., eds.
  Proceedings of the Second Workshop on Algorithm Engineering and Experiments (ALENEX'00), 2000, 300pp.

REFEREED ARTICLES

Most papers below are available in Postscript PS form and some also in Portable Data Format PDF

Papers on Gene Rearrangements

• Kothari, M., and Moret, B.M.E., "An experimental evaluation of inversion- and transposition-based genomic distances", Proc. 3rd IEEE Symp. on Comput. Intelligence in Bioinformatics and Comput. Biol. CIBCB'07, Honolulu, accepted, to appear.
• Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., and Moret, B.M.E., "Approximating the true evolutionary distance between two genomes," ACM J. Experimental Algorithmics, accepted, to appear (special issue on best papers from ALENEX'05). PS PDF
• Wang, L.-S., Jansen, R.K., Moret, B.M.E., Raubeson, L.A., and Warnow, T., "Distance-based genome rearrangement phylogeny," Journal of Molecular Evolution 63, 4 (2006), 473-483. PDF
• Swenson, K.M., Pattengale, N.D., and Moret, B.M.E., "A framework for orthology assignment from gene rearrangement data," Proc. 3rd RECOMB Workshop on Comparative Genomics (RECOMBCG'05), Dublin (Ireland), in Lecture Notes in Computer Science 3678, 153-166, Springer Verlag (2005). PS PDF
• Liu, T., Tang, J., and Moret, B.M.E., "Quartet methods for phylogeny reconstruction from gene orders," Proc. 11th Computing and Combinatorics Conference (COCOON'05), Kunming (China), in Lecture Notes in Computer Science 3595, 63-73, Springer Verlag (2005). PS PDF
• Tang, J., and Moret, B.M.E., "Linear programming for phylogenetic reconstruction based on gene rearrangements," Proc. 16th Symp. on Combinatorial Pattern Matching (CPM'05), Jeju Island (Korea), in Lecture Notes in Computer Science 3537, 406-416, Springer Verlag (2005). PS PDF
• Moret, B.M.E., and Warnow, T., "Advances in phylogeny reconstruction from gene order and content data," in Molecular Evolution: Producing the Biochemical Data, Part B, E.A. Zimmer and E.H. Roalson, eds., Vol. 395 of Methods in Enzymology, Elsevier (2005), 673-700. PS PDF
• Moret, B.M.E., Tang, J., and Warnow. T., "Reconstructing phylogenies from gene-content and gene-order data," in Mathematics of Evolution and Phylogeny, O. Gascuel, ed., Oxford Univ. Press (2005), 321-352. PS PDF
• Moret, B.M.E., "Computational challenges from the Tree of Life," Proc. 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), 3-16, SIAM Press (2005). PS PDF
• Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., and Moret, B.M.E., "Approximating the true evolutionary distance between two genomes," Proc. 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), 121-129, SIAM Press (2005). PS PDF
• Earnest-DeYoung, J.V., Lerat, E., and Moret, B.M.E., "Reversing gene erosion: Reconstructing ancestral bacterial genomes from gene-content and order data," Proc. 4th Workshop on Algorithms in Bioinformatics (WABI'04), in Lecture Notes in Computer Science 3240, 1-13, Springer Verlag (2004), PS PDF
• Marron, M., Swenson, K.M., and Moret, B.M.E., "Genomic distances under deletions and insertions," Theoretical Computer Science 325, 3 (2004), 347-360 (special issue on best papers from COCOON'03). PS PDF
• Tang, J., Moret, B.M.E., Cui, L., and dePamphilis, C.W., "Phylogenetic reconstruction from arbitrary gene-order data," Proc. 4th IEEE Conf. on Bioinformatics and Bioengineering (BIBE'04), 592-599, IEEE Press (2004). PS PDF
• Tang, J., and Moret, B.M.E., "Phylogenetic reconstruction from gene rearrangement data with unequal gene contents," Proc. 8th Workshop on Algorithms and Data Structures (WADS'03), in Lecture Notes in Computer Science 2748, Springer Verlag, 2003, 37-46. PS PDF
• Marron, M., Swenson, K.M., and Moret, B.M.E., ``Genomic distances under deletions and insertions," Proc. 9th Combinatorics and Computing Conf. (COCOON'03), in Lecture Notes in Computer Science 2697, Springer Verlag, 2003, 537-547. PS PDF
• Tang, J., and Moret, B.M.E., "Scaling up accurate phylogenetic reconstruction from gene-order data," Proc. 11th Conf. on Intelligent Systems for Molecular Biology (ISMB'03), in in Bioinformatics 19 (Suppl. 1) (2003), i305-i312. PS PDF
• Moret, B.M.E., Bader, D.A., and Warnow, T., "High-performance algorithm engineering for computational phylogenetics," J. Supercomputing 22 (2002), 99-111 (special issue on best papers from ICCS'01). PS PDF
• Moret, B.M.E., Tang, J., Wang, L.-S., and Warnow, T., "Steps toward accurate reconstruction of phylogenies from gene-order data" (special issue on computational biology), J. Comput. Syst. Sci. 65, 3 (2002), 508-525. PS PDF
• Moret, B.M.E., Siepel, A.C., Tang, J., and Liu, T., "Inversion medians outperform breakpoint medians in phylogeny reconstruction from gene-order data," Proc. 2nd Workshop on Algorithms in Bioinformatics (WABI'02), Rome (2002), in Lecture Notes in Computer Science 2452, 521-536. PS PDF
• Moret, B.M.E., Wang, L.-S., and Warnow, T., "Towards New Software for Computational Phylogenetics," IEEE Computer 35, 7 (July 2002), 55-64 (special issue on Bioinformatics). PS PDF
• Wang, L.-S., Jansen, R.K., Moret, B.M.E., Raubeson, L., and Warnow, T., "Fast phylogenetic methods for the analysis of genome rearrangement data: an empirical study," Proc. 7th Pacific Symp. on Biocomputing (PSB 2002), Hawaii, World Scientific Pub. (2002), 524-535. PS PDF PDF
• Bader, D.A., Moret, B.M.E., and Yan, M., "A linear-time algorithm for computing inversion distances between signed permutations with an experimental study," J. Comput. Biol. 8, 5 (2001), 483-491. PS (2MB) PDF
• Siepel, A., and Moret. B.M.E., "Finding an optimal inversion median: experimental results," Proc. 1st Workshop on Algorithms in Bioinformatics (WABI 01), Aarhus (2001), in Lecture Notes in Computer Science 2149, 189-203, Springer Verlag. PS PDF
• Bader, D.A., Moret, B.M.E., and Yan, M., "A linear-time algorithm for computing inversion distances between signed permutations with an experimental study," Proc. 7th Workshop on Algorithms and Data Structures (WADS 01), Providence (2001), in Lecture Notes in Computer Science 2125, 365-376, Springer Verlag. PS PDF
• Moret, B.M.E., Bader, D.A., and Warnow, T., "High-performance algorithmic engineering for computational phylogenetics," Proc. 2001 Int'l Conf. Computational Science (ICCS 2001), San Francisco (2001), in Lecture Notes in Computer Science 2074, 1012-1021, Springer Verlag. PS PDF
• Moret, B.M.E., Wang, L.-S., Warnow, T., and Wyman, S.K., "New approaches to phylogeny reconstruction from gene order data," 9th Conf. on Intelligent Systems for Molecular Biology (ISMB 2001), Copenhagen, in Bioinformatics 17 (2001), S165-S173; chosen as one of the 5 best papers at the conference. PS PDF
• Moret, B.M.E., Wyman, S., Bader, D.A., Warnow, T., and Yan, M., "A new implementation and detailed study of breakpoint analysis," Proc. 6th Pacific Symp. on Biocomputing (PSB 2001), Hawaii, World Scientific Pub. (2001), 583-594. PS PDF PDF
• Cosner, M.E., Jansen, R.K., Moret, B.M.E., Raubeson, L.A., Wang, L.-S., Warnow, T., and Wyman, S., "An empirical comparison of phylogenetic methods on chloroplast gene order data in Campanulaceae," in Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, D. Sankoff and J. Nadeau, eds., Kluwer Academic Publishers, Dordrecht, 2000, 99-121. PS PDF
• Cosner, M.E., Jansen, R.K., Moret, B.M.E., Raubeson, L.A., Wang, L.-S., Warnow, T., and Wyman, S., "A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data," Proc. 8th Conf. on Intelligent Systems for Molecular Biology (ISMB 2000), San Diego (2000), 104-115. PS PDF

Papers on Sequence-Based Phylogenetic Reconstruction

• Williams, T.L., Bader, D.A., Yan, M., and Moret, B.M.E., "High-performance phylogeny reconstruction under maximum parsimony," in Parallel Computing for Bioinformatics and Computational Biology, A.Y. Zomaya, ed., John Wiley & Sons, Chap. 16, pp. 369-394 (2006). PS PDF
• Roshan, U., Moret, B.M.E., Williams, T.L., and Warnow, T.. "Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees," Proc. 3rd IEEE Computational Systems Bioinformatics Conf. (CSB 2004), 98-109, IEEE Press (2004). PS PDF
• Roshan, U., Moret, B.M.E., Warnow, T., and Williams, T.L., "Performance of supertree methods on various dataset decompositions," in Phylogenetic Supertrees: Combining information to reveal the Tree of Life, O.R.P. Bininda-Edmonds, ed., Kluwer Acad. Publ., Dordrecht, 2004, 301-328. PS PDF
• St. John, K., Warnow, T., Moret, B.M.E., and Vawter, L., "Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining," J. Algorithms 48, 1 (2003), 173-193 (special issue on best papers from SODA'01). PS PDF
• Williams, T., and Moret, B.M.E., "An investigation of phylogenetic likelihood methods," Proc. 3rd IEEE Symp. on Bioinformatics and Bioengineering (BIBE'03), IEEE Press, 2003, 79-86. PS PDF
• Moret, B.M.E., Roshan, U., and Warnow, T., "Sequence length requirements for phylogenetic methods," Proc. 2nd Workshop on Algorithms in Bioinformatics (WABI'02), Rome (2002), in Lecture Notes in Computer Science 2452, 343-356. PS PDF
• Moret, B.M.E., Wang, L.-S., and Warnow, T., "Towards New Software for Computational Phylogenetics," IEEE Computer 35, 7 (July 2002), 55-64 (special issue on Bioinformatics). PS PDF
• Nakhleh, L., Moret, B.M.E., Roshan, U., St. John, K., Sun, J., and Warnow, T., "The accuracy of fast phylogenetic methods for large datasets," Proc. 7th Pacific Symp. on Biocomputing (PSB 2002), Hawaii, World Scientific Pub. (2002), 211-222. PS PDF PDF
• Moret, B.M.E., and Warnow, T., "Reconstructing optimal phylogenetic trees: A challenge in experimental algorithmics," in Experimental Algorithmics, Lecture Notes in Computer Science 2547, Springer Verlag, 2002, 163-180. PS PDF
• Warnow, T., Moret, B.M.E., and St. John, K., "Absolute convergence: true trees from short sequences," Proc. 12th Ann. Symp. Discrete Algs. (SODA 01), Washington DC, SIAM Press (2001), 186-195. PS PDF
• St. John, K., Warnow, T., Moret, B.M.E., and Vawter, L., "Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining," Proc. 12th Ann. Symp. Discrete Algs. (SODA 01), Washington DC, SIAM Press (2001), 196-205. PS PDF

Other Papers on Phylogenetic Reconstruction

• Pattengale, N.D., Gottlieb, E.J., and Moret, B.M.E., "Efficiently computing the Robinson-Foulds metric," J. Comput. Biol., accepted, to appear (special issue on best papers from RECOMB'06). PS PDF
• Morin, M.M., and Moret, B.M.E., "NETGEN: generating phylogenetic networks with diploid hybrids," Bioinformatics 22 (2006), 1921-1923. PDF
• Pattengale, N.D., and Moret, B.M.E., "A sublinear-time randomized approximation scheme for the Robinson-Foulds metric," Proc. 10th Int'l Conf. on Research in Comput. Molecular Biol. RECOMB'06, Venice (2006), in Lecture Notes in Computer Science 3909, 221-230. PS PDF
• Moret, B.M.E., Nakhleh, L., Warnow, T., Linder, C.R., Tholse, A., Padolina, A., Sun, J., and Timme, R., "Phylogenetic networks: modeling, reconstructibility, and accuracy," IEEE/ACM Trans. on Computational Biology and Bioinformatics 1, 1 (2004), 13-23. PS PDF
• Nakhleh, L., Sun, J., Warnow, T., Linder, R., Moret, B.M.E., and Tholse, A., "Towards the development of computational tools for evaluating phylogenetic network reconstruction methods," Proc. 8th Pacific Symp. on Biocomputing (PSB 2003), Hawaii, World Scientific Pub. (2003), 315-326. PS PDF
• Bader, D.A., Moret, B.M.E., and Vawter, L., "Industrial applications of high-performance computing for phylogeny reconstruction," Proc. SPIE Conf. on Commercial Appls. for High-Perf. Comput. ITComm 2001, Denver (2001), 159-168. PS PDF

Papers on Algorithmics, Computational Geometry, and Graph Algorithms

• Moret, B.M.E., "Computational challenges from the Tree of Life," Proc. 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), 3-16, SIAM Press (2005). PS PDF
• Moret, B.M.E., Bader, D.A., and Warnow, T., "High-performance algorithm engineering for computational phylogenetics," J. Supercomputing 22 (2002), 99-111 (special issue on best papers from ICCS'01). PS PDF
• Moret, B.M.E., "Towards a discipline of experimental algorithmics," in Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M.H. Goldwasser, D.S. Johnson, and C.C. McGeoch, eds, DIMACS Monographs 59, 197-213, American Mathematical Society, Providence, 2002. PS PDF
• Moret, B.M.E., and Warnow, T., "Reconstructing optimal phylogenetic trees: A challenge in experimental algorithmics," in Experimental Algorithmics, Lecture Notes in Computer Science 2547, Springer Verlag, 2002, 163-180. PS PDF
• Bader, D.A., Moret, B.M.E., and Sanders, P., "Algorithm engineering for parallel computation," in Experimental Algorithmics, Lecture Notes in Computer Science 2547, Springer Verlag, 2002, 1-23. PS PDF
• Doddi, S., Marathe, M., and Moret, B.M.E., "Point set labeling with specified positions," Int'l J. Comput. Geom. & Appls. 12, 1-2 (2002), 29-66 (special issue on best papers from SoCG'00).
• Bader, D.A., Ilendula, A.K., Moret, B.M.E., and Weisse-Bernstein, N.R., "Using PRAM algorithms on a uniform-memory-access shared-memory architecture" Proc. 5th Workshop on Algorithm Engineering (WAE 01), Aarhus (2001), in Lecture Notes in Computer Science 2141, 129-144, Springer Verlag. PS PDF
• Moret, B.M.E., and Shapiro, H.D., "Algorithms and experiments: the new (and the old) methodology," J. Univ. Computer Sci. 7, 5 (2001), 434-446. PS PDF
• Moret, B.M.E., Bader, D.A., and Warnow, T., "High-performance algorithmic engineering for computational phylogenetics," Proc. 2001 Int'l Conf. Computational Science (ICCS 2001), San Francisco (2001), in Lecture Notes in Computer Science 2074, 1012-1021, Springer Verlag. PS PDF
• Doddi, S., Marathe, M., and Moret, B.M.E., "Point labeling with specified positions," Proc. 16th Ann. ACM Symp. on Comput. Geometry (SoCG 2000), Hong Kong, 2000, 182--190. PS PDF
• McGeoch, C.C., and Moret, B.M.E., "How to present a paper on experimental work with algorithms," SIGACT News 30, 4 (1999), 85-90. PS PDF
• Goldberg, A.V., and Moret, B.M.E., "Combinatorial Algorithms Test Sets (CATS): The ACM/EATCS Platform for Experimental Research," Proc. 10th Ann. Symp. Discrete Algs. (SODA 99), Baltimore, SIAM Press (1999), 913-914. PS PDF
• Heileman, G.L., Abdallah, C.T., Moret, B.M.E., and Smith, B.J., "Dynamical systems representation of open address hash functions," Proc. 10th Ann. Symp. Discrete Algs. (SODA 99), Baltimore, SIAM Press (1999), 919-920.
• Collins, M.J., and Moret, B.M.E., "Improved lower bounds for the link length of rectilinear spanning paths in grids," Information Processing Letters 68, 6 (1998), 317-319. PS PDF
• Moret, B.M.E., "Bridging the gap between theory and practice: ACM's Journal of Experimental Algorithms," J. Electronic Publishing 3, 1 (1997).
• Moret, B.M.E., Collins, M.J., Saia, J, and Ling, Y., "Ice rinks and cruise missiles: sweeping a simple polygon," Proc. 1st Workshop on Algorithm Engineering (WAE 97), Venice, 1997. PS PDF
• Doddi, S., Marathe, M.V., Mirzaian, A., Moret, B.M.E., and Zhou, B., "Map labeling and its generalizations," Proc. 8th Ann. Symp. on Discrete Algs.(SODA 97), New Orleans, SIAM Press (1997), 148-157. PS PDF
• Boroujerdi, A., and Moret, B.M.E., "Persistent linked structures at constant worst-case cost," Proc. 8th Int'l Conf. Comput. & Info. (ICCI 96), Waterloo (1996), 68-78. PS
• Chen, Z., Holle, A.T., Moret, B.M.E., Saia, J., and Boroujerdi, A., "Network routing models applied to aircraft routing problems," Proc. Winter Simulation Conf., Arlington (1995), 1200-1206. PS
• Boroujerdi, A., and Moret, B.M.E., "Persistency in computational geometry," Proc. 7th Canadian Conf. Comp. Geometry (CCCG 95), Québec (1995), 241-246. PS
• Kooshesh, A.A., and Moret, B.M.E., "Folding a simple polygon: a paradigm for computational geometry," Proc. ACM Comp. Science Conf., Nashville (1995), 114-118. PS
• Moret, B.M.E., and Boroujerdi, A., "Spatial data structures in simulation and planning," Proc. 11th Ann. Conf. on Command and Control Decision Aids, Monterey (1994), 719-723. PS
• Moret, B.M.E., and Shapiro, H.D., "An empirical assessment of algorithms for constructing a minimum spanning tree," DIMACS Monographs 15 (1994), 99-117. PS
• Moret, B.M.E., Boroujerdi, A., Dong, C., and Ma, Q., "Joint routing in networks," NETFLOW93 (Network Optimization Theory and Practice), Centro Studi Cappuccini, San Miniato, Italy (1993), 175-180. PS
• Helman, P., Moret, B.M.E., and Shapiro, H.D., "An exact characterization of greedy structures," SIAM J. Discrete Math. 6, 2 (1993), 274-283.
• Moret, B.M.E., Boroujerdi, A., Dong, C., and Ma, Q., "Jointly optimal routing," Proc. 10th Ann. Conf. on Command and Control Decision Aids, Washington (1993).
• Kooshesh, A.A., and Moret, B.M.E., "Three-coloring the vertices of a triangulated simple polygon," Pattern Recognition 25, 4 (1992), 443.
• Helman, P., Moret, B.M.E., and Shapiro, H.D., "An exact characterization of greedy structures," Proc. 2nd Conf. on Integer Programming and Combinatorial Optimization (IPCO 92), Pittsburgh (1992), 287-297. PS
• Moret, B.M.E., and Shapiro, H.D., "How to find a minimum spanning tree in practice," Proc. Conf. on New Results and New Trends in Computer Science, Graz, Austria (1991), in Lecture Notes in Computer Science 555, Springer Verlag, 192-203. PS
• Moret, B.M.E., and Shapiro, H.D., "An empirical analysis of algorithms for constructing a minimum spanning tree," Proc. 2nd Workshop on Data Structures and Algorithms (WADS 91), Ottawa, CA (1991), in Lecture Notes in Computer Science 519, Springer Verlag, 400-411. PS
• Kooshesh, A.A., and Moret, B.M.E., "Folding triangulated simple polygons: structural and algorithmic results," Proc. 3rd Int'l Conf. on Information and Computing (ICCI-91), Ottawa, CA (1991), in Lecture Notes in Computer Science 497, Springer Verlag, 102-110. PS
• Abrahamson, K., Fellows, M.R., Langston, M.A., and Moret, B.M.E., "Constructive complexity," Discrete Applied Math. 34 (1991), 3-16.
• Kooshesh, A.A., Moret, B.M.E., and Szekely, L.L., "Improved bounds for the prison yard problem," Congressus Numerantium 76 (1990), 145-149.
• Tseng, C.T., and Moret, B.M.E., "A method for the choice of smoothing parameters," Mathematical & Computer Modelling 13, 9 (1990), 1-16.
• Tseng, C.T., and Moret, B.M.E., "A new method for one-dimensional linear feature transformations," Pattern Recognition 23, 7 (1990), 745-752.
• Tseng, C.T., and Moret, B.M.E., "The design of a non-parametric classifier," Proc. 10th Int'l Conf. on Pattern Recognition (ICPR 90), Atlantic City (1990), Vol. I, 428-432. PS

Last updated October 24, 2006