Publications (since 1990) 
This page is for archival use only. Please use the
publications page
at EPFL, my new institution.
Copyright Notice:
The documents accessible through these links are included by the authors
as a means to ensure convenient electronic dissemination of technical
work on a noncommercial basis. Copyright and all rights therein are
maintained by the copyright holders (the authors or the publishers),
notwithstanding that they have offered their works here electronically.
It is understood that all persons copying this information will adhere
to the terms and constraints invoked by each author's and publisher's
copyright. In particular, these works may not be reposted without
permission of the copyright holders.
TEXTBOOKS

Moret, B.M.E.
The Theory of Computation.
AddisonWesley, 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.
BenjaminCummings 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 ACMSIAM 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 transpositionbased 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., EarnestDeYoung, 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.,
"Distancebased genome rearrangement phylogeny,"
Journal of Molecular Evolution 63, 4 (2006), 473483.
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,
153166, 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,
6373, 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,
406416, 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), 673700.
PS PDF

Moret, B.M.E., Tang, J., and Warnow. T.,
"Reconstructing phylogenies from genecontent and geneorder data,"
in Mathematics of Evolution and
Phylogeny, O. Gascuel, ed., Oxford Univ. Press (2005), 321352.
PS
PDF

Moret, B.M.E.,
"Computational challenges from the Tree of Life,"
Proc. 7th Workshop on Algorithm Engineering and Experiments
(ALENEX'05),
316, SIAM Press (2005).
PS
PDF

Swenson, K.M., Marron, M., EarnestDeYoung, 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),
121129, SIAM Press (2005).
PS
PDF

EarnestDeYoung, J.V., Lerat, E., and Moret, B.M.E.,
"Reversing gene erosion: Reconstructing ancestral bacterial genomes from
genecontent and order data,"
Proc. 4th Workshop on Algorithms in Bioinformatics
(WABI'04), in
Lecture Notes in Computer Science 3240, 113, 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), 347360
(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 geneorder data,"
Proc. 4th IEEE Conf. on Bioinformatics and Bioengineering
(BIBE'04), 592599, 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, 3746.
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, 537547.
PS
PDF

Tang, J., and Moret, B.M.E.,
"Scaling up accurate phylogenetic reconstruction from geneorder data,"
Proc. 11th Conf. on Intelligent Systems for Molecular Biology
(ISMB'03), in
in Bioinformatics 19 (Suppl. 1) (2003), i305i312.
PS
PDF

Moret, B.M.E., Bader, D.A., and Warnow, T.,
"Highperformance algorithm engineering for computational phylogenetics,"
J. Supercomputing 22 (2002), 99111
(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 geneorder data"
(special issue on computational biology),
J. Comput. Syst. Sci. 65, 3 (2002), 508525.
PS
PDF

Moret, B.M.E., Siepel, A.C., Tang, J., and Liu, T.,
"Inversion medians outperform breakpoint medians in phylogeny reconstruction
from geneorder data,"
Proc. 2nd Workshop on Algorithms in Bioinformatics
(WABI'02),
Rome (2002), in
Lecture Notes in Computer Science
2452, 521536.
PS
PDF

Moret, B.M.E., Wang, L.S., and Warnow, T.,
"Towards New Software for Computational Phylogenetics,"
IEEE
Computer 35, 7 (July 2002), 5564
(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), 524535.
PS
PDF
PDF

Bader, D.A., Moret, B.M.E., and Yan, M.,
"A lineartime algorithm for computing inversion distances between signed
permutations with an experimental study,"
J. Comput. Biol. 8, 5 (2001), 483491.
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, 189203,
Springer Verlag.
PS
PDF

Bader, D.A., Moret, B.M.E., and Yan, M.,
"A lineartime 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, 365376,
Springer Verlag.
PS
PDF

Moret, B.M.E., Bader, D.A., and Warnow, T.,
"Highperformance algorithmic engineering for computational phylogenetics,"
Proc. 2001 Int'l Conf. Computational Science (ICCS 2001),
San Francisco (2001), in
Lecture Notes in Computer Science 2074, 10121021,
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), S165S173; 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), 583594.
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, 99121.
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), 104115.
PS
PDF
Papers on SequenceBased Phylogenetic Reconstruction

Williams, T.L., Bader, D.A., Yan, M., and Moret, B.M.E.,
"Highperformance phylogeny reconstruction under maximum parsimony,"
in Parallel Computing for Bioinformatics and Computational Biology,
A.Y. Zomaya, ed., John Wiley & Sons, Chap. 16, pp. 369394 (2006).
PS
PDF

Roshan, U., Moret, B.M.E., Williams, T.L., and Warnow, T..
"RecIDCM3: A fast algorithmic technique for reconstructing large
phylogenetic trees,"
Proc. 3rd IEEE Computational Systems Bioinformatics Conf.
(CSB 2004), 98109, 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. BinindaEdmonds, ed., Kluwer Acad. Publ., Dordrecht, 2004, 301328.
PS
PDF

St. John, K., Warnow, T., Moret, B.M.E., and Vawter, L.,
"Performance study of phylogenetic methods: (unweighted) quartet methods
and neighborjoining,"
J. Algorithms 48, 1
(2003), 173193 (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, 7986.
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, 343356.
PS
PDF

Moret, B.M.E., Wang, L.S., and Warnow, T.,
"Towards New Software for Computational Phylogenetics,"
IEEE
Computer 35, 7 (July 2002), 5564 (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), 211222.
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, 163180.
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), 186195.
PS
PDF

St. John, K., Warnow, T., Moret, B.M.E., and Vawter, L.,
"Performance study of phylogenetic methods: (unweighted) quartet methods
and neighborjoining,"
Proc. 12th Ann. Symp. Discrete Algs. (SODA 01), Washington DC,
SIAM Press (2001), 196205.
PS
PDF
Other Papers on Phylogenetic Reconstruction

Pattengale, N.D., Gottlieb, E.J., and Moret, B.M.E.,
"Efficiently computing the RobinsonFoulds 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), 19211923.
PDF

Pattengale, N.D., and Moret, B.M.E., "A sublineartime randomized
approximation scheme for the RobinsonFoulds metric," Proc.
10th Int'l Conf. on Research in Comput. Molecular Biol.
RECOMB'06,
Venice (2006), in
Lecture Notes in Computer Science 3909, 221230.
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), 1323.
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), 315326.
PS
PDF

Bader, D.A., Moret, B.M.E., and Vawter, L.,
"Industrial applications of highperformance computing for phylogeny reconstruction,"
Proc. SPIE Conf. on Commercial Appls. for HighPerf. Comput. ITComm 2001, Denver (2001), 159168.
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),
316, SIAM Press (2005).
PS
PDF

Moret, B.M.E., Bader, D.A., and Warnow, T.,
"Highperformance algorithm engineering for computational phylogenetics,"
J. Supercomputing 22 (2002), 99111
(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, 197213,
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, 163180.
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, 123.
PS
PDF

Doddi, S., Marathe, M., and Moret, B.M.E.,
"Point set labeling
with specified positions,"
Int'l J. Comput. Geom. & Appls. 12, 12 (2002),
2966 (special issue on best papers from SoCG'00).

Bader, D.A., Ilendula, A.K., Moret, B.M.E., and WeisseBernstein, N.R.,
"Using PRAM algorithms on a uniformmemoryaccess sharedmemory architecture"
Proc. 5th Workshop on Algorithm Engineering (WAE 01), Aarhus (2001), in
Lecture Notes in Computer Science 2141, 129144, 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), 434446.
PS
PDF

Moret, B.M.E., Bader, D.A., and Warnow, T.,
"Highperformance algorithmic engineering for computational phylogenetics,"
Proc. 2001 Int'l Conf. Computational Science (ICCS 2001),
San Francisco (2001), in
Lecture Notes in Computer Science 2074, 10121021, 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, 182190.
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), 8590.
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), 913914.
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), 919920.

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), 317319.
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), 148157.
PS
PDF

Boroujerdi, A., and Moret, B.M.E., "Persistent linked structures at
constant worstcase cost,"
Proc. 8th Int'l Conf. Comput. & Info. (ICCI 96),
Waterloo (1996), 6878.
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), 12001206.
PS

Boroujerdi, A., and Moret, B.M.E., "Persistency in computational geometry,"
Proc. 7th Canadian Conf. Comp. Geometry
(CCCG 95),
Québec (1995), 241246.
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), 114118.
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), 719723.
PS

Moret, B.M.E., and Shapiro, H.D., "An empirical assessment of algorithms
for constructing a minimum spanning tree,"
DIMACS Monographs 15 (1994), 99117.
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), 175180.
PS

Helman, P., Moret, B.M.E., and Shapiro, H.D.,
"An exact characterization
of greedy structures," SIAM J. Discrete Math. 6,
2 (1993), 274283.

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.,
"Threecoloring
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), 287297.
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, 192203.
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, 400411.
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 (ICCI91),
Ottawa, CA (1991), in
Lecture Notes in Computer Science 497, Springer Verlag, 102110.
PS

Abrahamson, K., Fellows, M.R., Langston, M.A., and Moret, B.M.E.,
"Constructive complexity,"
Discrete Applied Math. 34 (1991), 316.

Kooshesh, A.A., Moret, B.M.E., and Szekely, L.L., "Improved bounds for
the prison yard problem," Congressus Numerantium 76
(1990), 145149.

Tseng, C.T., and Moret, B.M.E.,
"A method for
the choice of smoothing parameters," Mathematical & Computer
Modelling 13, 9 (1990), 116.

Tseng, C.T., and Moret, B.M.E.,
"A new method
for onedimensional linear feature transformations,"
Pattern Recognition 23, 7 (1990), 745752.

Tseng, C.T., and Moret, B.M.E., "The design of a nonparametric
classifier,"
Proc. 10th Int'l Conf. on Pattern Recognition (ICPR 90),
Atlantic City (1990), Vol. I, 428432.
PS
Last updated October 24, 2006