@string{cacm = "Commun.\ {ACM}"} @string{nar = "Nucleic Acids Research"} @string{cabios = "Computer Applications in the Biosciences (CABIOS)"} @string{jmb = "J. of Molecular Biology"} @string{pnas = "Proc. of the Natnl. Acad. of Sciences of the U. S. A."} @string{me = "Methods in Enzymology"} @string{molevol = "Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences"} @string{ipl = "Information Processing Letters"} @string{siam = "Society for Industrial and Applied Mathematics (SIAM)"} @misc{ACP:Knuth, note = {Atemporal}, x = "************************************************************" } @techreport{AFS92, author = {R. Agarwala and D. Fern\'andez-Baca and G. Slutzki}, address = {226 Atanasoff, Ames IA 50011}, institution = {Dept. of Computer Science, Iowa State University}, month = {July}, number = {TR 92-19}, title = {Fast Algorithms for Inferring Evolutionary Trees}, year = {1992} } @article{AGMML90, author = {Stephen F. Altschul and Warren Gish and Webb Miller and Eugene W. Myers and David J. Lipman}, journal = jmb, pages = {403--410}, title = {A Basic Local Alignment Search Tool}, volume = {215}, year = {1990} } @book{AHU74, author = {A. V. Aho and J. E. Hopcroft and J. D. Ullman}, address = {Reading, MA}, publisher = {Addison-Wesley}, title = {The Design and Analysis of Computer Algorithms}, year = {1974} } @article{AJ88, author = {A. W. Appel and G. J. Jacobson}, journal = cacm, number = {5}, pages = {572--578,585}, title = {The World's Fastest {Scrabble} Program}, volume = {31}, year = {1988} } @article{AKD91, author = {M. Adams, J. Kelley, J. Dubnick at al.}, journal = {Science}, pages = {1651--1656}, title = {Complementary {DNA} sequencing: Expressed sequence tags and human genome project}, volume = {252}, year = {1991} } @inproceedings{AMM94, author = {A. A. M. Almeida and J. Meidanis and A. Moriya}, booktitle = {Anais do {XXI} Semin\'ario Integrado de Software e Hardware}, editor = {Nivio Ziviani}, pages = {533--545}, publisher = {Sociedade Brasileira de Computa\c{c}\~ao}, title = {Um Sistema para Aux\'{\i}lio na Montagem de Fragmentos de {DNA}}, year = {1994} } @inproceedings{AMM94e, author = {A. A. M. Almeida and J. Meidanis and A. Moriya}, booktitle = {{XXI} Software and Hardware Symposium}, editor = {Nivio Ziviani}, note = {In Portuguese}, pages = {533--545}, publisher = {Brazilian Computer Society}, title = {A System for {DNA} Fragment Assembly}, year = {1994} } @incollection{Apos85, author = {A. Apostolico}, booktitle = {Combinatorial Algorithms on Words}, editor = {A. Apostilico and Z. Galil}, pages = {85--96}, publisher = {Springer-Verlag}, series = {NATO ASI Series F: Computer and System Sciences}, title = {The Myriad Virtues of Subword Trees}, volume = {12}, year = {1985} } @incollection{BA90, author = {D. Bacon and W. Anderson}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {438--447}, publisher = {Academic Press}, series = me, title = {Multiple Sequence Comparison}, volume = {183}, year = {1990} } @article{Baez91, author = {R. A. Baeza-Yates}, journal = {Theoretical Computer Science}, number = {2}, pages = {363--376}, title = {Searching Subsequences}, volume = {78}, year = {1991} } @article{BB65, author = {Leonard E. Baum and Patrick Billingsley}, journal = {Ann. Math. Stat.}, number = {6}, pages = {1835--1839}, title = {Asymptotic Distributions for the Coupon {Collector's} Problem}, volume = {36}, year = {1965} } @inproceedings{BCDTT92, author = {P. Bertolazzi and R. Cohen and G. Di Batista and R. Tamassia and I. Tollis}, booktitle = {Proc. of the Third Scandinavian Workshop on Algorithm Theory}, pages = {272--283}, series = {Lecture Notes in Computer Sciences}, title = {How to Draw a Series-Parallel Digraph}, volume = {621}, year = {1992} } @incollection{BCGH90, author = {C. Burks and M. J. Cinkosky and P. Gilna and J. E.-D. Hayden and Y. Abe and E. J. Atencio and S. Barnhouse and D. Benton and C. A. Buenafe and K. E. Cumella and D. B. Davison and D. B.}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {3--22}, publisher = {Academic Press}, series = me, title = {{GenBank}: Current Status and Future Directions}, volume = {183}, year = {1990} } @article{Beke64, author = {A. B{\'e}k{\'e}ssy}, journal = {Magyar Tud. Akad. Mat. {Kutat\'o} Int. {K\"ozl.}}, number = {1--2}, pages = {133-141}, title = {On Classical Occupancy Problems, {II}}, volume = {9A}, year = {1964} } @book{Bent86, author = {Jon Bentley}, address = {Reading, Mass.}, publisher = {Addison-Wesley}, title = {Programming Pearls}, year = {1986} } @article{Benz59, author = {S. Benzer}, journal = pnas, pages = {1607--1620}, title = {On the topology of the genetic fine structure}, volume = {45}, year = {1959} } @article{BG88, author = {Alan A. Bertossi and Alessandro Gori}, journal = {{SIAM} J. Disc. Math.}, number = {3}, pages = {317--327}, title = {Total Domination and Irredundance in Weighted Interval Graphs}, volume = {1}, year = {1988} } @incollection{BGH90, author = {Winona C. Barker and David G. George and Lois T. Hunt}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {31--49}, publisher = {Academic Press}, series = me, title = {Protein Sequence Database}, volume = {183}, year = {1990} } @inproceedings{BJLTY91, author = {A. Blum and T. Jiang and M. Li and J. Tromp and M. Yannakakis}, booktitle = {Proc.\ 23rd {ACM} Symposium on Theory of Computing}, pages = {328--336}, title = {Linear approximation of shortest superstrings}, year = {1991} } @article{BKS92, author = {W. W. Bein and J. Kamburowski and M. F. M. Stallman}, journal = {{SIAM} J. Computing}, number = {6}, pages = {1112--1129}, title = {Optimal Reduction of Two-Terminal Directed Acyclic Graphs}, volume = {21}, year = {1992} } @Article{BMM98, author = {Barbosa, M. M. and Mello, C. P. and Meidanis, J.}, title = {Local conditions for edge-colouring of cographs}, journal = {Congressus Numerantium}, year = 1998, volume = 133 } @inproceedings{BO83, author = {M. Ben-Or}, booktitle = {15th ACM Symp. on Theory of Computing}, month = {May}, pages = {80--86}, title = {Lower bounds for algebraic computation trees}, year = {1983} } @book{BS96, author = {Eric Bach and Jeff Shallit}, month = {Aug}, note = {{ISBN} 0-262-02405-5 (v.1)}, publisher = {{MIT} Press}, title = {Algorithmic Number Theory, Volume {I}: {Efficient} Algorithms}, year = {1996} } @InProceedings{BM2002, author = {Marília D. V. Braga and João Meidanis}, title = {An algorithm that builds a set of strings given its overlap graph}, booktitle = {Latin American Theoretical Informatics (LATIN02)}, year = 2002, editor = {S. Rajsbaum}, volume = 2286, series = {Lecture Notes in Computer Science}, address = {Cancun, Mexico}, month = {April}, publisher = {Spinger Verlag} } @Article{BDL+2001, author = {Marília D. V. Braga and Zanoni Dias and Tzy Li Lin and João Meidanis and José A. A. Quitzau and Felipe R. da Silva and Guilherme P. Telles}, title = {Bioinformatics of the Sugarcane {EST} Project}, journal = {Genetics and Molecular Biology}, volume = {24}, number = {1--4}, pages = {9--15}, year = 2001 } @unpublished{Bsho89, author = {N. H. Bshouty}, note = {Unpublished}, title = {Euclidean GCD Algorithm is Not Optimal}, year = {1989} } @article{BW84, author = {T. H. Byers and M. S. Waterman}, journal = {Oper. Res.}, pages = {1381--1384}, title = {Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming}, volume = {32}, year = {1984} } @inproceedings{CM2001, author = {F. R. Cerqueira and J. Meidanis}, booktitle = {Anais do XXVIII Semin{\'a}rio Integrado de Software e Hardware}, month = aug, publisher = {Universidade Federal do Ceará}, title = {Algorithms for Large-scale DNA Sequencing}, year = {2001} } @inproceedings{CM2001e, author = {F. R. Cerqueira and J. Meidanis}, booktitle = {Proc.~of the XXVIII Integrated Seminar on Software and Hardware - SEMISH}, month = aug, publisher = {Federal University of Ceará}, title = {Algorithms for Large-scale {DNA} Sequencing}, year = {2001}, note = {In Portuguese} } @InProceedings{CM2001sat, author = {F. R. Cerqueira and J. Meidanis}, title = {Recombination and Iteration: A Recipe for Fragment Assembly}, booktitle = {RECOMB Satellite Meeting on DNA Sequence Assembly}, year = 2001, address = {Los Angeles}, month = {May}, organization = {University of Southern California} } Título: "Recombination and Iteration: A Recipe for Fragment Assembly". Autores: Fábio Ribeiro Cerqueira e João Meidanis. Local: University of Southern California, Los Angeles - California. Periodo: 19-20 de maio de 2001. @unpublished{CBEEW92, author = {G. Churchil and C. Burks and M. Eggert and M. Engle and M. Waterman}, note = {Submitted for publication}, title = {Assembling {DNA} sequence fragments by shuffling and simulated annealing}, year = {1992} } @techreport{CBEEW93, author = {G. Churchil and C. Burks and M. Eggert and M. Engle and M. Waterman}, institution = {Los Alamos National Laboratory}, number = {{LA-UR-93-2287}}, title = {Assembling {DNA} sequence fragments by shuffling and simulated annealing}, year = {1993} } @book{CBG82, author = {John Horton Conway and Elwyn R. Berlekamp and Richard Guy}, note = {ISBN: 0-120-91102-7}, publisher = {Academic Press}, title = {Winning Ways : For Your Mathematical Play}, year = {1982} } @article{CH92, author = {Chen, W.-Q. and Hunkapiller, T.}, journal = {{DNA} Sequence}, pages = {335--342}, title = {Sequencing accuracy of large {DNA} sequencing projects}, volume = {2}, year = {1992} } @article{CKNOS95, author = {D. G. Corneil and H. Kim and S. Natarajan and S. Olariu and A. P. Sprague}, journal = {{Information Perocessing Letters}}, pages = {99-104}, title = {Simple Linear Time Recognition of Unit Interval Graphs}, volume = {55}, year = {1995} } @article{CR73, author = {S. A. Cook and R. A. Reckhow}, journal = {JCCS}, pages = {354--375}, title = {Time Bounded Random Access Machines}, volume = {7}, year = {1973} } @incollection{CSB90, author = {J.-M. Claverie and I. Sauvaget and L. Bougueleret}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {237--252}, publisher = {Academic Press}, series = me, title = {$k$-tuple Frequency Analysis: From Intron/Exon Discrimination to {T}-Cell Epitope Mapping}, volume = {183}, year = {1990} } @article{CZOM95, author = {K.-M. Chao and J. Zhang and J. Ostell and W. Miller}, journal = cabios, number = {2}, pages = {147--153}, title = {A local alignment tool for very long {DNA} sequences}, volume = {11}, year = {1995} } @manual{Darwin, author = {Gaston H. Gonnet}, address = {Switzerland}, month = nov, organization = {Informatik {ETH} {Z\"urich}}, title = {A tutorial introduction to Computational Biochemistry using {D}arwin}, year = {1992} } @article{DCH91, author = {Dankaert, Anne and Chappey, Colombe and Hazout, Serge}, journal = cabios, number = {4}, pages = {509--513}, title = {{`Size Leap'} Algorithm: An Efficient Extraction of the Longest Common Motifs from a Molecular Sequence Set. {A}pplication to the {DNA} Sequence Reconstruction}, volume = {7}, year = {1991} } @article{DHS84, author = {J. Devereux and P. Haeberli and D. Smithies}, journal = nar, pages = {387--395}, title = {A Comprehensive Set of Sequence Analysis Programs for the {VAX}}, volume = {12}, year = {1984} } @inproceedings{DM2001, author = {Z. Dias and J. Meidanis}, booktitle = {Proc. of SPIRE'2001 - String Processing and Information Retrieval Symposium}, title = {Genome Rearrangements Distance by Fusion, Fission, and Transposition is Easy}, pages = {250--253}, year = {2001} } @inproceedings{DM2002, author = {Z. Dias and J. Meidanis}, booktitle = {Proc. of SPIRE'2002 - String Processing and Information Retrieval Symposium}, title = {Sorting by Prefix Transpositions}, pages = {65--76}, year = {2002} } @article{DN82, author = {J. Dumas and J. Ninio}, journal = nar, number = {1}, pages = {197--206}, title = {Efficient Algorithms for Folding and Comparing Nucleic Acid Sequences}, volume = {10}, year = {1982} } @incollection{DSO78, author = {M. Dayhoff and R. M. Schwartz and B. C. Orcutt}, address = {Silver Spring, {MD}}, booktitle = {Atlas of Protein Sequence and Structure}, editor = {M. Dayhoff}, note = {Supplement 3}, pages = {345--352}, publisher = {National Biomedical Research Foundation}, title = {A Model of Evolutionary Change in Proteins}, volume = {5}, year = {1978} } @article{DT88, author = {G. Di{B}atista and R. Tamassia}, journal = {Theoretical Computer Science}, pages = {175--198}, title = {Algorithms for Plane Representations of Acyclic Digraphs}, volume = {61}, year = {1988} } @article{Dwas69, author = {Meyer Dwass}, journal = {Journal of Combinatorial Theory}, pages = {258--261}, title = {More Birthday Surprises}, volume = {7}, year = {1969} } @article{EB93, author = {Engle, M.L. and Burks, C.}, journal = {Genomics}, pages = {286--288}, title = {Artificially Generated Data Sets for Testing {DNA} Fragment Assembly Algorithms}, volume = {16}, year = {1993} } @article{EB94, author = {Engle, M.L. and Burks, C}, journal = cabios, pages = {567--568}, title = {{GenFrag} 2.1: New Features for More Robust Fragment Assembly Benchmarks}, volume = {10}, year = {1994} } @article{ER61, author = {P. {Erd\H{o}s} and A. {R\'enyi}}, journal = {Magyar Tud. Akad. Mat. {Kutat\'o} Int. {K\"ozl.}}, note = {In: Selected papers of Alfred R{\'e}nyi. Edited by P{\'a}l Tur{\'a}n. Budapest, Akademiai Kiado, 1976, pp.\ 617--622.}, pages = {215-220}, title = {On a Classical Problem of Probability Theory}, volume = {6A}, year = {1961} } @article{Esca73, author = {F. Escalante}, journal = {Abh. Math. Sem. Univ. Hamburg}, pages = {59--6}, title = {{\"U}ber iterierte Clique-Graphen}, volume = {39}, year = {1973} } @incollection{FD90, author = {D. Feng and R. Doolittle}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {375--387}, publisher = {Academic Press}, series = me, title = {Progressive Alignment and Phylogenetic Tree Construction of Protein Sequences}, volume = {183}, year = {1990} } @article{Fels89, author = {J. Felsenstein}, journal = {Cladistics}, pages = {164--166}, title = {{PHYLIP} -- {P}hylogeny {I}nference {P}ackage ({V}ersion 3.2)}, volume = {5}, year = {1989} } @article{Fic82, author = {J. Fickett}, journal = nar, pages = {5303--5317}, title = {Recognition of Protein Coding Regions in {DNA} Sequences}, volume = {10}, year = {1982} } @article{Floy90, author = {Edwin T. Floyd}, journal = {Dr.\ {Dobb's} Journal}, month = Nov, title = {An Existential Dictionary}, year = {1990} } @inproceedings{FMM94, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, booktitle = {Anais da Academia Brasileira de {Ci\^encias}}, number = {4}, title = {On Edge-Colouring Indifference Graphs}, volume = {66}, year = {1994} } @inproceedings{FMM95, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, booktitle = {Anais da I Oficina Nacional em Problemas Combinat\'orios}, month = {Feb}, organization = {IME-USP}, pages = {11--14}, title = {Edge-Colouring, Indifference Graphs, and Odd Maximum Degree Graphs}, year = {1995} } @inproceedings{FMM95a, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, address = {Valpara\'{\i}so, Chile}, booktitle = {Proc.\ of the II Latin American Theoretical Informatics}, editor = {R. Baeza-Yates and E. Goles and P. V. Poblete}, month = Apr, pages = {286--299}, publisher = {Springer-Verlag}, series = {LNCS}, title = {On Edge-Colouring Indifference Graphs}, volume = {911}, year = {1995} } @inproceedings{FMM95b, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, booktitle = {Anais da II Oficina Nacional em Problemas Combinat\'orios}, month = {Nov}, organization = {DCC-UNICAMP}, pages = {26--38}, title = {Local Conditions for Edge Coloring}, year = {1995} } @article{FMM95cn, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, journal = {Congressus Numerantium}, pages = {170--176}, title = {A Greedy Method for Edge-Coloring Odd Maximum Degree Doubly Chordal Graphs}, volume = {111}, year = {1995} } @article{FMM95ipl, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, journal = {Information Processing Letters}, pages = {179--184}, title = {A Linear-Time Algorithm for Proper Interval Graph Recongnition}, volume = {56}, year = {1995} } @Article{FMMO2003, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello and C. Ortiz}, title = {Decompositions for the edge colouring of reduced indifference graphs}, journal = {Theoretical Computer Science}, year = 2003, volume = 297, number = {1--3}, pages = {145--155}, month = {March} } @techreport{FMM95pb, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, address = {{\tt reltec@dcc.unicamp.br}}, institution = {Computer Science Dept., University of Campinas}, number = {{DCC-95-04}}, title = {A Greedy Method for Edge-Coloring Odd Maximum Degree Doubly Chordal Graphs}, year = {1995} } @inproceedings{FMM96, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, booktitle = {XXIII {Semin\'ario} Integrado de Software e Hardware}, editor = {Roberto S. M. de Barros and Paulo R. F. Cunha}, pages = {415--420}, title = {On the Edge-Coloring of Split Graphs}, year = {1996} } @inproceedings{FMM96e, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, booktitle = {Proc.~of the XXIII Integrated Seminar on Software and Hardware - SEMISH}, editor = {Roberto S. M. de Barros and Paulo R. F. Cunha}, pages = {415--420}, title = {On the Edge-Coloring of Split Graphs}, year = {1996} } @article{FMM97tcs, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, journal = {Theoretical Computer Science}, pages = {91--106}, title = {On Edge-colouring Indifference Graphs}, volume = {181}, year = {1997} } @Article{FMM99, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, title = {Total-chromatic number and chromatic index of dually chordal graphs}, journal = {Information Processing Letters}, year = 1999, volume = 70, number = 3, pages = {147--152} } @Article{FMM2000, author = {C. M. H. de Figueiredo and J. Meidanis and C. P. de Mello}, title = {Local conditions for edge-coloring}, journal = {Journal of Combinatorial Mathematics and Combinatorial Computing}, year = 2000, volume = 32, pages = {79--91} } @article{GB90, author = {G. H. Gonnet and R. A. Baeza-Yates}, journal = ipl, pages = {271--274}, title = {An Analysis of the Karp-Rabin String Matching Algorithm}, volume = {34}, year = {1990} } @TechReport{FM2004, author = {V. J. Fortuna and J. Meidanis}, title = {Sorting the Reverse Permutation by Prefix Transpositions}, institution = {Institute of Computing, University of Campinas}, year = 2004, number = {IC-04-04}, month = {April} } @TechReport{TM2003, author = {G. P. Telles and J. Meidanis}, title = {Building PQR trees in almost-linear time}, institution = {Institute of Computing, University of Campinas}, year = 2003, number = {IC-03-26}, month = {November} } @article{GC92, author = {Mark Guyer and Howard Cann}, journal = {Science}, pages = {67--76}, title = {A comprehensive genetic linkage map of the human genome}, volume = {258}, year = {1992} } @article{GDB83, author = {M. Gribskov and J. Devereux and R. Burgess}, journal = nar, pages = {539--549}, title = {The Codon Preference Plot: Graphic Analysis of Protein Coding Sequences and Prediction of Gene Expression}, volume = {12}, year = {1983} } @inproceedings{GI93, author = {R. Grossi and G. F. Italiano}, booktitle = {Proc.\ 1st South American Workshop on String Processing}, editor = {R. Baeza-Yates and N. Ziviani}, month = {sep}, pages = {57--76}, title = {Suffix Trees and Their Applications in String Algorithms}, year = {1993} } @book{GJ79, author = {Garey, Michael R. and Johnson, David S.}, address = {New York}, publisher = {Freeman}, title = {Computers and Intractability: A Guide to the Theory of NP-Completeness}, year = {1979} } @book{GK90, author = {D. H. Greene and D. E. Knuth}, address = {Boston}, edition = {third}, publisher = {Birkh{\"a}user}, title = {Mathematics for the Analysis of Algorithms}, year = {1990} } @article{GLL82, author = {U. I. Gupta and D. T. Lee and J. Y.-T. Leung}, journal = {Networks}, pages = {459--467}, title = {Efficient Algorithms for Interval Graphs and Circular-Arc Graphs}, volume = {12}, year = {1982} } @book{GLS88, author = {M. {Gr\"otschel} and L. {Lov\'asz} and A. Schrijver}, publisher = {Springer-Verlag}, title = {Geometric Algorithms and Combinatorial Optimization}, year = {1988} } @article{GLS92, author = {Dan Gusfield and Gad M. Landau and Baruch Schieber}, journal = ipl, pages = {181-185}, title = {An Efficient Algorithm for the All Pairs Suffix-Prefix Problem}, volume = {41}, year = {1992} } @Article{GM2002ac, author = {Marisa Gutierrez and Joao Meidanis}, title = {On Clique Graph Recognition}, journal = {Ars Combinatoria}, year = 2002, volume = 63, pages = {207--210} } @article{GM2003dam, author = "Marisa Gutierrez and Joao Meidanis", title = "Recognizing clique graphs of directed edge path graphs", journal = "Discrete Applied Mathematics", volume = "126", issue = "2--3", pages = "297--304", year = "2003", month = "March" } @Article{GM2003mc, author = {Marisa Gutierrez and Joao Meidanis}, title = {Preimage, Image, and Iterated Image of the Clique Operator}, journal = {Matemática Contemporânea}, year = 2003, volume = 25, pages = {107--123}, note = {ISSN 0103-9059} } @InProceedings{GM2001, author = {Marisa Gutierrez and João Meidanis}, title = {The Clique Operator, Set Families, and Their Properties}, booktitle = {Electronic Notes in Discrete Mathematics}, volume = {7}, publisher = {Elsevier Science Publishers}, editor = {Jayme Szwarcfiter and Siang Song}, year = {2001} } @Article{GM2001jbcs, author = {Gutierrez, Marisa and Meidanis, João}, title = {Algebraic theory for the clique operator}, journal = {J. Braz. Comp. Soc.}, year = 2001, volume = 7, number = 3, pages = {53--64}, note = {ISSN 0104-6500} } @InProceedings{GM98, author = {M. Gutierrez and J. Meidanis}, title = {On the Clique Operator}, booktitle = {Proc. of {LATIN}'98 - Latin American Theoretical Informatics}, pages = {261--272}, year = 1998, volume = 1380, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @article{GMS80, author = {J. Gallant and D. Maier and J. Storer}, journal = {J. Comput. System Sci.}, number = {1}, pages = {50--58}, title = {On Finding Minimal Length Superstrings}, volume = {20}, year = {1980} } @article{GMSR79, author = {T. Gingerias and J. Milazzo and D. Sciaky and R. Roberts}, journal = nar, pages = {529--545}, title = {Computer Programs for Assembly of {DNA} Sequences}, volume = {7}, year = {1979} } @book{Golu80, author = {Martin Charles Golumbic}, publisher = {Academic Press}, title = {Algorithmic Graph Theory and Perfect Graphs}, year = {1980} } @article{Gonn81, author = {Gaston H. Gonnet}, journal = {JACM}, month = Apr, number = {2}, pages = {289--304}, title = {Expected Length of the Longest Probe Sequence in Hash Code Searching}, volume = {28}, year = {1981} } @article{Goto90a, author = {Osamu Gotoh}, journal = {Bull. Math. Biol.}, number = {3}, pages = {359--373}, title = {Optimal Sequence Alignment Allowing for Long Gaps}, volume = {52}, year = {1990} } @article{Grah81, author = {S. Graham}, journal = {Acta Arith.}, pages = {163--179}, title = {On {Linnik's} Constant}, volume = {39}, year = {1981} } @article{GT92, author = {S. W. Guo and E. A Thompson}, journal = {Biometrics}, pages = {361--372}, title = {Performing the Exact Test of Hardy-Weinberg Proportion for Multiple Alleles}, volume = {48}, year = {1992} } @book{HC83, author = {Arthur W. Ham and David H. Cormack}, publisher = {Editora Guanabara Koogan}, title = {Histologia}, year = {1983} } @book{Heij87, author = {Heijne, Gunnar von}, address = {San Diego, CA}, publisher = {Academic Press}, title = {Sequences Analysis in Molecular Biology: Treasure Trove or Trivial Pursuit}, year = {1987} } @incollection{Hein90, author = {Jotun Hein}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {626--645}, publisher = {Academic Press}, series = me, title = {Unified Approach to Alignment and Phylogenies}, volume = {183}, year = {1990} } @article{HHM90, author = {Xiaoqiu Huang and Ross C. Hardison and Webb Miller}, journal = cabios, number = {4}, pages = {373--381}, title = {A Space-Efficient algorithm for Local Similarities}, volume = {6}, year = {1990} } @article{Hirs75, author = {D. Hirshberg}, journal = cacm, pages = {341--343}, title = {A linear space algorithm for computing maximal common subsequences}, volume = {18}, year = {1975} } @article{HJZCC94, author = {Holly A. Hammond and Li Jin and Y. Zhong and C. Thomas Caskey and Ranajit Chakraborty}, journal = {Am. J. Hum. Genet.}, pages = {175--189}, title = {Evaluation of 13 Short Tandem Repeat Loci for Use in Personal Identification Applications}, volume = {55}, year = {1994} } @inproceedings{HL91, author = {Michael D. Hutton and Anna Lubiw}, booktitle = {Proc. of the 2nd Symposium on Discrete Algorithms}, pages = {203--211}, title = {Upward Planar Drawing of Single Source Acyclic Digraphs}, year = {1991} } @article{HM91, author = {X. Huang and W. Miller}, journal = {Advances in Applied Mathematics}, pages = {337--357}, title = {Linear-Space Local Similarity Algorithm}, volume = {12}, year = {1991} } @article{Hod92, author = {John Hodgson}, journal = {Biotechnology}, month = jul, number = {7}, title = {Sequencing and Mapping Efforts in {``Model Organisms''}}, volume = {10}, year = {1992} } @book{HS88, author = {J. Hindley and R. Staden}, publisher = {Elsevier Biomedical Press}, title = {{DNA} sequencing}, year = {1988} } @book{Hua82, author = {{Hua Loo Keng}}, publisher = {Springer-Verlag}, title = {Introduction to Number Theory}, year = {1982} } @article{Huan92, author = {X. Huang}, journal = {Genomics}, pages = {18--25}, title = {A Contig Assembly Program Based on Sensitive Detection of Fragment Overlaps}, volume = {14}, year = {1992} } @inproceedings{Huan95, author = {X. Huang}, booktitle = {4th DIMACS Implementation Challenge - Fragment Assembly}, editor = {M. Vingron}, title = {An Improved Sequence Assembly Program}, year = {1995} } @book{HW79, author = {G. H. Hardy and E. M. Wright}, edition = {fifth}, publisher = {Oxford University Press}, title = {An Introduction to the Theory of Numbers}, year = {1979} } @incollection{HWB90, author = {Steven Henikoff and James C. Wallace and Joseph P. Brown}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {111--132}, publisher = {Academic Press}, series = me, title = {Finding Protein Similarities with Nucleotide Sequence Databases}, volume = {183}, year = {1990} } @article{HZ77, author = {J. W. Hunt and T. G. Szymanski}, journal = cacm, month = {May}, number = {5}, pages = {350--353}, title = {A Fast Algorithm for Computing Longest Common Subsequences}, volume = {20}, year = {1977} } @techreport{IP92, author = {Telba Irony and Carlos Alberto de {Bragan\c{c}a} Pereira}, address = {Statistics Dept., IME-USP, Cx.\ Postal 20570, 01498-970 {S\~ao} Paulo, Brazil}, institution = {University of {S\~ao} Paulo}, month = Sep, number = {{RT-MAE-9216}}, title = {Bayesian Hypothesis Test: Using Surface Integrals to Distribute Prior Information Among the Hypotheses}, year = {1992} } @book{IR82, author = {K. Ireland and M. Rosen}, publisher = {Springer-Verlag}, series = {Graduate Texts in Mathematics}, title = {A Classical Introduction to Modern Number Theory}, volume = {84}, year = {1982} } @article{Ivch71, author = {G. I. Ivchenko}, journal = {Theory of Probability and its Applications}, number = {2}, pages = {293--307}, title = {Limit Theorems in an Occupancy Problem}, volume = {16}, year = {1971} } @book{JK77, author = {N. L. Johnson and S. Kotz}, address = {New York}, publisher = {John Wiley \& Sons}, title = {Urn Models and Their Application}, year = {1977} } @inproceedings{IKLMRWJ93, author = {W. Istvanick and A. Kryder and G. Lewandowski and J. Meidanis and A. Rang and S. Wyman and D. Joseph}, booktitle = {Proc. of the Twenty-Sixth Annual Hawaii Int'l Conf on System Sciences}, month = {jan}, pages = {534--543}, title = {Dynamic Methods for Fragment Assembly in Large Scale Genome Sequencing Projects}, volume = {I}, year = {1993} } @article{JMD86, author = {Johnston, R.E. and Mackenzie, J. M.Jr. and Dougherty, W.G.}, journal = nar, number = {1}, pages = {517--527}, title = {Assembly of overlapping {DNA} sequences by a program written in BASIC for 64k CP/M and {MS-DOS IBM-compatible} microcomputers}, volume = {14}, year = {1986} } @inproceedings{JMT92, author = {D. Joseph and J. Meidanis and P. Tiwari}, booktitle = {Proc.\ of the Third Scandinavian Workshop on Algorithm Theory}, pages = {326--337}, series = {Lecture Notes in Computer Science}, title = {Determining {DNA} Sequence Similarity Using Maximum Independent Set Algorithms for Interval Graphs}, volume = {621}, year = {1992} } @inproceedings{JMW88, author = {B. Just and F. {Meyer auf der Heide} and A. Wigderson}, booktitle = {{STACS} 88}, editor = {R. Cori and M. Wirsing}, pages = {29--37}, publisher = {Springer-Verlag}, title = {On Computations with Integer Division}, year = {1988} } @incollection{KC90, author = {Patricia Kahn and Graham Cameron}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {23--31}, publisher = {Academic Press}, series = me, title = {{EMBL} Data Library}, volume = {183}, year = {1990} } @phdthesis{Kece91, author = {John D. Kececioglu}, school = {The University of Arizona}, title = {Exact and approximation algorithms for {DNA} sequence reconstruntion}, year = {1991} } @incollection{Keil90, author = {Borivoj Keil}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {50--60}, publisher = {Academic Press}, series = me, title = {Cooperation between databases and Scientific Community}, volume = {183}, year = {1990} } @unpublished{KM91, author = {J. Kececioglu and E. Myers}, note = {Unpublished}, title = {A Robust and Automatic Fragment Assembly System}, year = {1991} } @techreport{KM92, author = {John D. Kececioglu and Eugene W. Myers}, institution = {The University of Arizona}, month = Oct, number = {TR 92-37}, title = {Combinatorial algorithms for {DNA} sequence assembly}, year = {1992} } @article{KM95, author = {J. D. Kececioglu and E. W. Myers}, journal = {Algorithmica}, pages = {7--51}, title = {Combinatorial Algorithms for {DNA} Fragment Assembly}, volume = {13}, year = {1995} } @book{KnuthI, author = {D. E. Knuth}, address = {Reading, Massachusetts}, publisher = {Addison-Wesley}, title = {The Art of Computer Programming}, volume = {1}, year = {1973} } @book{KnuthII, author = {D. E. Knuth}, address = {Reading, Massachusetts}, publisher = {Addison-Wesley}, title = {The Art of Computer Programming}, volume = {2}, year = {1981} } @article{KR87, author = {R. Karp and M. Rabin}, journal = {IBM J.\ of Research and Development}, pages = {249--260}, title = {Efficient Randomized Pattern-Matching Algorithms}, volume = {31}, year = {1987} } @unpublished{Kry92, author = {A. Kryder}, note = {Manuscript}, title = {A Statistical Package for Genome Sequencing}, year = {1992} } @book{KSC78, author = {Valentin F. Kolchin and Boris A. {Sevast'yanov} and Vladimir P. Chistyakov}, address = {Washington, D.C.}, publisher = {V. H. Winston \& Sons}, series = {Scripta Series in Mathematics}, title = {Random Allocations}, year = {1978} } @inproceedings{KW90, author = {S. Kannan and T. Warnow}, booktitle = {Proc.\ 31st Symp.\ on Foundations of Computer Science}, pages = {362--371}, title = {Inferring evolutionary history from {DNA} sequences}, year = {1991} } @article{LAK89, author = {D. Lipman and S. Altschul and J. Kececioglu}, journal = pnas, pages = {4412--4415}, title = {A Tool for Multiple Sequence Alignment}, volume = {86}, year = {1989} } @book{Lawl76, author = {Eugene L. Lawler}, address = {New York}, publisher = {Holt, Rinehart and Winston}, title = {Combinatorial Optimization: Networks and Matroids}, year = {1976} } @inproceedings{Li90, author = {Ming Li}, booktitle = {Proc.\ 31st Symposium on Foundations of Computer Science}, pages = {125--134}, title = {Towards a {DNA} sequencing theory (learning a string)}, year = {1990} } @unpublished{LIJ92, author = {Gary Lewandowski and Wendy Istvanick and Deborah Joseph}, note = {In preparation}, title = {A Multiple Sequence Alignment Tool}, year = {1992} } @article{Linn44, author = {U. V. Linnik}, journal = {Mat. Sbornik}, pages = {139--178}, title = {On the Least Prime in an Arithmetic Progression}, volume = {15}, year = {1944} } @techreport{LK92, author = {C. L. Lucchesi and T. Kowaltowski}, address = {DCC -- IMECC -- UNICAMP, Cx. Postal 6065, 13081-970, Campinas, SP, Brazil}, institution = {Dept. of Computer Science, State University of Campinas}, note = {To appear in {\em Software --- Practice and Experience}}, number = {{DCC}-01/92}, title = {Applications of Finite Automata Representing Large Vocabularies}, year = {1992} } @article{LK93, author = {C. L. Lucchesi and T. Kowaltowski}, journal = {Software --- Practice and Experience}, number = {1}, pages = {15-30}, title = {Applications of finite automata representing large vocabularies}, volume = {23}, year = {1993} } @inproceedings{LLM88, author = {M. Litzkow and M. Livny and M. W. Mutka}, address = {San Jose, California}, booktitle = {Proceedings of the 8th International Conference on Distributed Computing Systems}, month = jun, title = {Condor - {A} Hunter of Idle Workstations}, year = {1988} } @article{LMT89, author = {Eric Lander and Jill P. Mesirov and Washington Taylor}, journal = {J. Supercomp.}, pages = {255--269}, title = {Study of Protein Sequence Comparison Metrics on the Connection Machine {CM-2}}, year = {1989} } @mastersthesis{Loza96, author = {L. A. P. Lozada}, school = {DCC-UNICAMP}, title = {{T\'opicos} na Classe dos Grafos Clique}, year = {1996} } @article{LP85, author = {D. J. Lipman and W. R. Pearson}, journal = {Science}, pages = {1435--1441}, title = {Rapid and Sensitive Protein Similarity Search}, volume = {227}, year = {1985} } @article{LW88, author = {Eric S. Lander and Michael S. Waterman}, journal = {Genomics}, pages = {231--239}, title = {Genomic Mapping by Fingerprinting Random Clones: A Mathematical Analysis}, volume = {2}, year = {1988} } @incollection{M90, author = {Sanzo Miyazawa}, booktitle = {Computers and {DNA}}, editor = {George I. Bell and Thomas M. Marr}, pages = {47--61}, publisher = {Addison-Wesley}, title = {{DNA} Data Bank of {J}apan: Present Status and Future Plans}, year = {1990} } @article{MadH85, author = {Meyer auf der Heide, F.}, journal = {JACM}, number = {4}, pages = {929--937}, title = {Lower Bounds for Solving Linear Diophantine Equations on Random Access Machines}, volume = {32}, year = {1985} } @book{Man89, author = {U. Manber}, publisher = {Addison-Wesley}, title = {Introduction to Algorithms}, year = {1989} } @article{Mart83, author = {Hugo M. Martinez}, journal = nar, number = {13}, pages = {4629--4634}, title = {An Efficient Method for Finding Repeats in Molecular Sequences}, volume = {11}, year = {1983} } @article{MCS81, author = {J. Messing and R. Crea and P. H. Seeburg}, journal = nar, pages = {309--321}, title = {A System for Shotgun {DNA} Sequencing}, volume = {9}, year = {1981} } @techreport{Meid90, author = {J. Meid{\^a}nis}, institution = {Computer Science Dept., University of Wisconsin-Madison}, number = {978}, title = {Lower Bounds for Arithmetic Problems}, year = {1990} } @article{Meid91, author = {J. Meidanis}, journal = ipl, pages = {83--87}, title = {Lower Bounds for Arithmetic Problems}, volume = {38}, year = {1991} } @phdthesis{Meid92, author = {J. Meidanis}, school = {University of Wisconsin-Madison}, title = {Algorithms for Problems in Computational Genetics}, year = {1992} } @inproceedings{Meid93, author = {J. Meidanis}, address = {Belo Horizonte, Brazil}, booktitle = {Proc.\ First South American Workshop on String Processing}, editor = {R. Baeza-Yates and N. Ziviani}, month = {September}, organization = {UFMG}, pages = {123--134}, title = {Rethinking the {DNA} Fragment Assembly Problem}, year = {1993} } @TechReport{Meid93rt23, author = {J. Meidanis}, title = {Rethinking the {DNA} Fragment Assembly Problem}, institution = {Institute of Computing, University of Campinas}, year = 1993, number = {DCC-23/93}, month = {September} } @TechReport{Meid93rt27, author = {J. Meidanis}, title = {An Unified Characterization of Chordal, Interval, Indifference, and Other Classes of Graphs}, institution = {Institute of Computing, University of Campinas}, year = 1993, number = {DCC-27/93}, month = {September} } @inproceedings{Meid95, author = {J. Meidanis}, address = {Valpara\'{\i}so, Chile}, booktitle = {Proc.\ of the II South American Workshop on String Processing}, editor = {R. Baeza-Yates and U. Manber}, month = Apr, pages = {27--37}, title = {Distance and Similarity in the Presence of Nonincreasing Gap-Weighting Functions}, year = {1995} } @inproceedings{Meid95chall, author = {J. Meidanis}, booktitle = {Proc.\ of the IV DIMACS Implementation Challenge - Fragment Assembly}, editor = {M. Vingron}, title = {{FAT} - {A} {Fragment Assembly Toolkit}}, year = {1995} } @InProceedings{Meid97, author = {J. Meidanis}, title = {Biologia Molecular Computacional}, booktitle = {Escola Regional de Informática }, year = 1997, editor = {J. P. Kitajima}, organization = {Regional Minas e Centro-Oeste da SBC} } @InCollection{Meid99, author = {J. Meidanis}, title = {A Simple Toolkit for {DNA} Fragment Assembly}, booktitle = {Mathematical Support for Molecular Biology}, pages = {271--288}, publisher = {American Mathematical Society}, year = 1999, editor = {M. Farach-Colton and F. S. Roberts and M. Vingron and M. Waterman}, volume = 47, series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science} } @inproceedings{MELM96, author = {de Mendon\c{c}a Neto, C. F. X. and P. Eades and C. L. Lucchesi and J. Meidanis}, booktitle = {Computing: the Australasian Theory Symposium}, editor = {P. Eades}, note = {Submitted}, title = {NP-Hardness Results for Tention-Free Layout}, year = {1996} } @MastersThesis{Meid84e, author = {J. Meidanis}, title = {The Moving Frame Method in Conformal Geometry}, school = {University of São Paulo}, year = 1984 } @InProceedings{Meid2003, author = {J. Meidanis}, title = {Current Challenges in Bioinformatics}, booktitle = {Proc. of SPIRE'2003 - String Processing and Information Retrieval Symposium}, pages = {16--27}, year = 2003, editor = {Mario A. Nascimento and Edleno Silva de Moura and Arlindo L. Oliveira}, volume = 2857, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @Article{MBV2002, author = {J. Meidanis and M. D. V. Braga and S. Verjovski-Almeida}, title = {Whole-Genome Analysis of Transporters in the Plant Pathogen \textit{Xylella fastidiosa}}, journal = {Microbiology and Molecular Biology Reviews}, year = 2002, volume = 66, number = 2, pages = {272--299}, month = {June} } @unpublished{MJ92, author = {J. Meidanis and D. Joseph}, note = {Submitted to the SIAM Symposium on Discrete Algorithms}, title = {Hashing and Back Prediction Methods for Computing Sequence Similarity for Fragment Assembly}, year = {1992} } @unpublished{MJ92pp, author = {J. Meidanis and D. Joseph}, note = {Unpublished}, title = {Hashing and Back-Prediction Methods for Computing Sequence Similarity} } @unpublished{MJ92wl, author = {J. Meidanis and D. Joseph}, note = {Unpublished}, title = {On the Weakest Link in an Interval Graph and Applications to {DNA} Frgament Assembly} } @article{ML81, author = {J. Maizel and R. Lenk}, journal = pnas, pages = {7665--7669}, title = {Enhanced Graphic Matrix Analysis of Nucleic Acid and Protein Sequences}, volume = {78}, year = {1981} } @InCollection{Meid2003global, author = {J. Meidanis}, title = {Global alignment}, booktitle = {Nature Encyclopedia of the Human Genome}, publisher = {Nature Publishing Group}, year = 2003, editor = {David N. Cooper}, month = {June}, note = {ISBN 0-333-80386-8} } @InCollection{Meid2003asm, author = {J. Meidanis}, title = {Sequence assembly}, booktitle = {Nature Encyclopedia of the Human Genome}, publisher = {Nature Publishing Group}, year = 2003, editor = {David N. Cooper}, month = {June}, note = {ISBN 0-333-80386-8} } @Misc{Meid2003com, author = {J. Meidanis}, title = {Bioinformática na Indústria}, howpublished = {ComCiência --- Revista Eletrônica de Jornalismo Científico, no. 46}, month = {Aug}, year = 2003, note = {http://www.comciencia.br} } @article{MM88a, author = {Eugene W. Myers and Webb Miller}, journal = cabios, number = {1}, pages = {11--17}, title = {Optimal alignments in linear space}, volume = {4}, year = {1988} } @article{MM88b, author = {Webb Miller and Eugene W. Myers}, journal = {Bull. Math. Biol.}, number = {2}, pages = {97--120}, title = {Sequence Comparison with Concave Weighting Functions}, volume = {50}, year = {1988} } @InProceedings{MM2004, author = {C. V. G. Mira and J. Meidanis}, title = {Analysis of Sorting by Transpositions based on Algebraic Formalism}, booktitle = {{RECOMB} Posters}, year = 2004, organization = {University of Califonia - San Diego} } @article{MM89, author = {E. W. Myers and W. Miller}, journal = {Bull. Math. Biol.}, pages = {5--37}, title = {Approximate matching of regular expressions}, volume = {51}, year = {1989} } @inproceedings{MM90, author = {U. Manber and G. Myers}, booktitle = {Proceedings of the First Annual ACM--SIAM Symposium on Discrete Algorithms}, pages = {319--327}, publisher = {SIAM}, title = {Suffix arrays: {A} new method for on--line string searches}, year = {1990}, comment = "A new data structure is described that can, in many situations, replace suffix trees and occupy less space without loss of time. In some situations suffix arrays can take longer to construct than suffix trees. This data structure allows questions of the form ``Is W a substring of A?'' to be answered in $O(|W| + \log |A|)$ time." } @inproceedings{MM95, author = {J. Meidanis and E. G. Munuera}, booktitle = {Proc.\ of the XV International Conference of the Chilean Computing Society}, editor = {N. Ziviani and J. Piquer and B. Ribeiro and R. Baeza-Yates}, month = {Nov}, pages = {275--283}, title = {A Simple Linear Time Algorithm for Binary Phylogeny}, year = {1995} } @techreport{MM95pq, author = {J. Meidanis and E. G. Munuera}, address = {{\tt reltec@dcc.unicamp.br}}, institution = {Computer Science Dept., University of Campinas}, number = {{DCC-95-21}}, title = {A Linear Time Algorithm for Binary Phylogeny Using {PQ}-Trees}, year = {1995} } @inproceedings{MM96, author = {J. Meidanis and E. G. Munuera}, address = {Recife, Brazil}, booktitle = {Proc.\ of the III South American Workshop on String Processing}, editor = {N. Ziviani and Ricardo Baeza-Yates and Katia {Guimar\~aes}}, month = {Aug}, pages = {194--202}, title = {A Theory for the Consecutive Ones Property}, year = {1996} } @article{MPT98, author = {J. Meidanis and O. Porto and G. P. Telles}, journal = {Discrete Applied Mathematics}, title = {On the consecutive ones property}, volume = 88, number = {1--3}, pages = {325--354}, year = 1998 } @book{MS94, author = {J. Meidanis and J. C. Setubal}, address = {Recife, Brazil}, publisher = {{IX} Escola de Computa\c{c}\~ao}, title = {Uma Introdu\c{c}\~ao \`a Biologia Computacional}, year = {1994} } @book{MS94e, author = {J. Meidanis and J. C. Setubal}, address = {Recife, Brazil}, publisher = {{IX} Brazilian Computing School}, title = {An Introduction To Computational Biology}, year = {1994} } @inproceedings{MS95, author = {J. Meidanis and J. C. Setubal}, address = {Valpara\'{\i}so, Chile}, booktitle = {Proc.\ of the II Latin American Theoretical Informatics}, editor = {R. Baeza-Yates and E. Goles and P. V. Poblete}, month = Apr, pages = {411--426}, publisher = {Springer-Verlag}, series = {LNCS}, title = {Multiple Alignment of Biological Sequences with Gap Flexibility}, volume = {911}, year = {1995} } @inproceedings{MST88a, author = {Y. Mansour and B. Schieber and P. Tiwari}, address = {Berlin, New York}, booktitle = {Proc. 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Comp.\ Sci.\ 372}, month = Jul, note = {Also in: Tech.\ Report TR 14272, IBM T. J. Watson Research Center, Yorktown Heights, NY, December 1988}, pages = {559--573}, publisher = {Springer-Verlag}, title = {Lower Bounds for Computations with the Floor Operation}, year = {1989} } @techreport{MST88b, author = {Y. Mansour and B. Schieber and P. Tiwari}, address = {Yorktown Heights, NY}, institution = {IBM T. J. Watson Research Center}, month = Dec, note = {To appear in {\em JACM\/}. Preliminary version in: Proc.\ 29th IEEE Symposium on Foundations of Computer Science, October 1988, pp.\ 54--63}, number = {TR 14272}, title = {A Lower Bound for Integer Greatest Common Divisor Computations}, year = {1988} } @article{MST88bold, author = {Y. Mansour and B. Schieber and P. Tiwari}, journal = {{\rm To appear in} JACM}, note = {Preliminary version in: Proc.\ 29th IEEE Symposium on Foundations of Computer Science, October 1988, pp.\ 54--63}, title = {A Lower Bound for Integer Greatest Common Divisor Computations}, year = {1991} } @article{MST91, author = {Y. Mansour and B. Schieber and P. Tiwari}, journal = {{\rm To appear in} SIAM J. Comput.}, note = {Preliminary version in: Proc.\ 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 372, Springer-Verlag, Berlin, New York, July 1989,}, number = {2}, title = {Lower Bounds for Computations with the Floor Operation}, volume = {20}, year = {1991} } @incollection{Mur90, author = {M. Murata}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {365--375}, publisher = {Academic Press}, series = me, title = {Three-Way {N}eedleman-{W}unsch Algorithm}, volume = {183}, year = {1990} } @book{MvH90, author = {C. K. Mathews and K. E. van Holde}, publisher = {Benjamin/Cummings}, title = {Biochemistry}, year = {1990} } @techreport{MVW95, author = {C. B. Medeiros and G. Vossen and M. Weske}, institution = {University of {M\"unster}}, number = {02/95-1}, title = {{WASA}: {A} Workflow-Based Architecture to Support Scientific Database Applications}, year = {1995} } @techreport{MVW95a, author = {J. Meidanis and G. Vossen and M. Weske}, institution = {University of {M\"unster}}, number = {23/95-I}, title = {Using Workflow Management in {DNA} Sequencing}, year = {1995} } @inproceedings{MVW96, author = {J. Meidanis and G. Vossen and M. Weske}, booktitle = {Proc.\ First IFCIS Conference on Cooperative Information Systems}, editor = {K. Aberer and A. Helal}, title = {Using Workflow Management in {DNA} Sequencing}, year = {1996} } @inproceedings{MWD97, author = {J. Meidanis and M. E. M. T. Walter and Z. Dias}, booktitle = {Anais do XXIV Semin{\'a}rio Integrado de Software e Hardware}, editor = {Paulo C{\'e}sar Masiero and Ros{\^a}ngela A. D. Penteado}, month = aug, pages = {119--131}, publisher = {Universidade de Bras{\'{\i}}lia}, title = {{Distância} de reversão de cromossomos circulares}, year = {1997} } @inproceedings{MWD97e, author = {J. Meidanis and M. E. M. T. Walter and Z. Dias}, booktitle = {Proc.~of the XXIV Integrated Seminar on Software and Hardware - SEMISH}, editor = {Paulo César Masiero and Rosângela A. D. Penteado}, month = aug, pages = {119--131}, publisher = {University de Brasília}, title = {Distância de reversão de cromossomos circulares}, year = {1997}, note = {In Portuguese} } @inproceedings{mwd97c, author = {J. Meidanis and M. E. M. T. Walter and Z. Dias}, booktitle = {Proc. of the Fourth South American Workshop on String Processing}, pages = {70--79}, series = {International Informatics Series}, publisher = {Carleton University Press}, volume = 8, title = {Transposition distance between a permutation and its reverse}, year = {1997} } @inproceedings{wdm98, author = {M. E. M. T. Walter and Z. Dias and J. Meidanis}, booktitle = {Proc. of SPIRE'98 - String Processing and Information Retrieval: A South American Symposium}, pages = {96--102}, title = {Reversal and Transposition Distance of Linear Chromosomes}, year = {1998} } @inproceedings{wdm2000, author = {M. E. M. T. Walter and Z. Dias and J. Meidanis}, booktitle = {Proc. of SPIRE'2000 - String Processing and Information Retrieval Symposium}, title = {A New Approach for Approximating the Transposition Distance}, year = {2000}, publisher = {IEEE Computer Society} } @Article{MWD2002, author = {J. Meidanis and M. E. M. T. Walter and Z. Dias}, title = {A Lower Bound on the Reversal and Transposition Diameter}, journal = {Journal of Computational Biology}, year = 2002, volume = 9, number = 5, pages = {743--745}, month = {October} } @InCollection{MD2000, author = {J. Meidanis and Z. Dias}, title = {An Alternative Algebraic Formalism for Genome Rearrangements}, booktitle = {Comparative Genomics}, pages = {213--223}, publisher = {Kluwer Academic Publishers}, year = 2000, editor = {David Sankoff and Joseph Nadeau} } @inproceedings{Myer92, author = {Gene Myers}, booktitle = {Proc.\ First Latin American Theoretical Informatics}, pages = {372--386}, series = {Lecture Notes in Computer Science}, title = {Approximate matching of network expressions with spacers}, volume = {583}, year = {1992} } @article{Myer95, author = {E. W. Myers}, journal = {J. Computational Biology}, number = {2}, pages = {275--290}, title = {Toward Simplifying and Accurately Formulating Fragment Assembly}, volume = {2}, year = {1995} } @article{NS88, author = {Kazuo Nishimura and Masaaki Sibuya}, journal = {Ann. Inst. Statist. Math.}, number = {1}, pages = {77--91}, title = {Occupancy With Two Types of Balls}, volume = {40}, year = {1988} } @article{NVS91, author = {A. Nayeem and J. Vila and H. A. Scheraga}, journal = {J. Comput. Chem.}, number = {5}, pages = {594--605}, title = {A Comparative Study of Simulated Annealing and {M}onte {C}arlo-with-minimization approaches to the minimum energy structures of polypeptides: ({M}et)-enkephalin}, volume = {12}, year = {1991} } @article{NW70, author = {Saul B. Needleman and Christian D. Wunsch}, journal = jmb, pages = {443--453}, title = {A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins}, volume = {48}, year = {1970} } @book{NW88, author = {G. L. Nemhauser and L. A. Wosley}, publisher = {John Wiley \& Sons}, title = {Integer and Combinatorial Oprimization}, year = {1988} } @article{Olar91, author = {Stephen Olariu}, journal = ipl, pages = {21--25}, title = {An optimal greedy heuristic to color interval graphs}, volume = {37}, year = {1991} } @book{PB85, author = {{Purdom, Jr.}, P. W. and C. A. Brown}, address = {New York}, publisher = {Holt, Rinehart and Winston}, title = {The Analysis of Algorithms}, year = {1985} } @article{PBPR89, author = {J. Posfai and A. Bhagwat and G. Posfai and R. Roberts}, journal = nar, pages = {2421--2435}, title = {Predictive Motifs Derived from Cytosine Methyltransferases}, volume = {17}, year = {1989} } @article{Pea91, author = {W. Pearson}, journal = {Genomics}, pages = {635--650}, title = {Searching Protein Sequence Libraries: Comparison of the Sensitivity and Selectivity of the {S}mith-{W}aterman and {FASTA} Algorithms}, volume = {11}, year = {1991} } @incollection{Pear90, author = {William R. Pearson}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {63--98}, publisher = {Academic Press}, series = me, title = {Rapid and Sensitive Sequence Comparison with {FASTP} and {FASTA}}, volume = {183}, year = {1990} } @article{Peev91, author = {K. Peeva}, journal = {Theoretical Computer Science}, number = {2}, pages = {269--285}, title = {Equivalence, Reduction and Minimization of Finite Automata over Semirings}, volume = {88}, year = {1991} } @article{PL88, author = {William R. Pearson and David J. Lipman}, journal = pnas, pages = {2444--2448}, title = {Improved Tools for Biological Sequence Comparison}, volume = {85}, year = {1988} } @incollection{PM92, author = {William R. Pearson and Webb Miller}, booktitle = {Numerical Computer Methods}, editor = {Ludwig Brand and Michael L. Johnson}, pages = {575--601}, publisher = {Academic Press}, series = me, title = {Dynamic Programming Algorithms for Biological Sequence Comparison}, volume = {210}, year = {1992} } @article{Poll75, author = {J. M. Pollard}, journal = {Bit}, pages = {331--334}, title = {A Monte Carlo Method for Factorization}, volume = {15}, year = {1975} } @inbook{PS81, author = {W. Paul and J. Simon}, pages = {331--340}, publisher = {Universit{\'e} de Gen{\`e}ve}, series = {Monographies de {l'Enseignement} Math{\'e}matique}, title = {Decision Trees and Random Access Machines}, volume = {30}, year = {1981} } @article{PSU84, author = {H. Peltola and H. {S\"oderlund} and E. Ukkonen}, journal = nar, pages = {307--321}, title = {{SEQAIDS}: A {DNA} Sequence Assembling Program Based on a Mathematical Model}, volume = {12}, year = {1984} } @article{Re62, author = {A. {R\'enyi}}, journal = {MTA Mat. Kut. Int. {K\"ozl}.}, pages = {203--214}, title = {Three New Proofs and a Generalization of a Theorem of {Irving} {Weiss}}, volume = {7A}, year = {1962} } @book{Robe89, editor = {Fred Roberts}, publisher = {Springer-Verlag}, title = {Applications of Combinatorics and Graph Theory to the Biological and Social Sciences}, year = {1989} } @article{RS62, author = {J. B. Rosser and L. Schoenfeld}, journal = {Ill. J. Math.}, pages = {64--94}, title = {Approximate Formulas for Some Functions of Prime Numbers}, volume = {6}, year = {1962} } @article{SAL91, author = {G. Schuler and S. Altschul and D. Lipman}, journal = {Proteins Struc. Func. Genet.}, pages = {180--190}, title = {A Workbench for Multiple Alignment Construction and Analysis}, volume = {9}, year = {1991} } @article{Sank72, author = {David Sankoff}, journal = pnas, number = {1}, pages = {4--6}, title = {Matching Sequences under Deletion/Insertion Constraints}, volume = {69}, year = {1972} } @Article{S+2000, author = {A. Simpson and others}, title = {The genome sequence of the plant pathogen \emph{{X}ylella fastidiosa}}, journal = {Nature}, year = 2000, volume = 406, pages = {151--157}, note = {This paper has more than one hundred authors (not shown), and J. Meidanis is one of them} } @Article{S+2000full, author = {A. J. G. Simpson and F.C. Reinach and P. Arruda and F. A. Abreu and M. Acencio and R. Alvarenga and L. M. C. Alves and J. E. Araya and G. S. Baia and C. S. Baptista and M. H. Barros and E. D. Bonaccorsi and S. Bordin and J. M. Bové and M. R. S. Briones and M. R. P. Bueno and A. A. Camargo and L. E. A. Camargo and D. M. Carraro and H. Carrer and N. B. Colauto and C. Colombo and F. F. Costa and M. C. R. Costa and C. M. Costa-Neto and L. L. Coutinho and M. Cristofani and E. Dias-Neto and C. Docena and H. El-Dorry and A. P. Facincani and A. J. S. Ferreira and V. C. A. Ferreira and J. A. Ferro and J. S. Fraga and S. C. França and M. C. Franco and M. Frohme and L. R. Furlan and M. Garnier and G. H. Goldman and M. H. S. Goldman and S. L. Gomes and A. Gruber and P. L. Ho and J. D. Hoheisel and M. L. Junqueira and E. L. Kemper and J.P. Kitajima and J. E. Krieger and E. E. Kuramae and F. Laigret and M. R. Lambais and L. C. C. Leite and E. G. M. Lemos and M. V. F. Lemos and S. A. Lopes and C. R. Lopes and J. A. Machado and M. A. Machado and A. M. B. N. Madeira and H. M. F. Madeira and C. L. Marino and M. V. Marques and E. A. L. Martins and E. M. F. Martins and A. Y. Matsukuma and C. F. M. Menck and E. C. Miracca and C. Y. Miyaki and C. B. Monteiro-Vitorello and D. H. Moon and M. A. Nagai and A. L. T. O. Nascimento and L. E. S. Netto and A. Nhani Jr and F. G. Nobrega and L. R. Nunes and M. A. Oliveira and M. C. de Oliveira and R. C. de Oliveira and D. A. Palmieri and A. Paris and B. R. Peixoto and G. A. G. Pereira and H. A. Pereira Jr and J. B. Pesquero and R. B. Quaggio and P. G. Roberto and V. Rodrigues and A. J. de M. Rosa and V. E. de Rosa Jr and R. G. de Sá and R. V. Santelli and H. E. Sawasaki and A. C. R. da Silva and A. M. da Silva and F. R. da Silva and and W. A. Silva and J. F. da Silveira and M. L. Z. Silvestri and W. J. Siqueira and A. A. de Souza and A. P. de Souza and M. F. Terenzi and D. Truffi and S. M. Tsai and M. H. Tsuhako and H. Vallada and M. A. Van Sluys and S. Verjovski-Almeida and A. L. Vettore and M. A. Zago and M. Zatz and J. Meidanis and J. C. Setubal}, title = {The genome sequence of the plant pathogen \emph{{X}ylella fastidiosa}}, journal = {Nature}, year = 2000, volume = 406, pages = {151--157} } @Article{S+2002, author = {A. C. R. da Silva and others}, title = {Comparison of the genomes of two \textit{Xanthomonas} pathogens with differing host specificities}, journal = {Nature}, year = 2002, volume = 417, pages = {459--463}, month = {May}, note = {This paper 65 authors (not shown), and J. Meidanis is one of them} } @Article{S+2002full, author = {A. C. R. da Silva and J. A. Ferro and F. C. Reinach and C. S. Farah and L. R. Furlan and R. B. Quaggio and C. B. Monteiro-Vitorello and M. A. Van Sluys and N. F. Almeida and L. M. C. Alves and A. M. do Amaral and M. C. Bertolini and L. E. A. Camargo and G. Camarotte and F. Cannavan and J. Cardozo and F. Chambergo and L. P. Ciapina and R. M. B. Cicarelli and L. L. Coutinho and J. R. Cursino-Santos and H. El-Dorry and J. B. Faria and A. J. S. Ferreira and R. C. C. Ferreira and M. I. T. Ferro and E. F. Formighieri and M. C. Franco and C. C. Greggio and A. Gruber and A. M. Katsuyama and L. T. Kishi and R. P. Leite and E. G. M. Lemos and M. V. F. Lemos and E. C. Locali and M. A. Machado and A. M. B. N. Madeira and N. M. Martinez-Rossi and E. C. Martins and J. Meidanis and C. F. M. Menck and C. Y. Miyaki and D. H. Moon and L. M. Moreira and M. T. M. Novo and V. K. Okura and M. C. Oliveira and V. R. Oliveira and H. A. Pereira and A. Rossi and J. A. D. Sena and C. Silva and R. F. de Souza and L. A. F. Spinola and M. A. Takita and R. E. Tamura and E. C. Teixeira and R. I. D. Tezza and M. Trindade dos Santos and D. Truffi and S. M. Tsai and F. F. White and J. C. Setubal and J. P. Kitajima}, title = {Comparison of the genomes of two \textit{Xanthomonas} pathogens with differing host specificities}, journal = {Nature}, year = 2002, volume = 417, pages = {459--463}, month = {May} } @article{SCH92, author = {Wei-Kuan Shih and T. C. Chen and Wen-Lian Hsu}, journal = {{SIAM} J. Computing}, number = {6}, pages = {1026--1046}, title = {An $O(n^2\log n)$ Algorithm for the {H}amiltonian {C}ycle Problem on Circular-Arc Graphs}, volume = {21}, year = {1992} } @techreport{Shav90, author = {J. W. Shavlik}, institution = {Computer Sciences Department, University of Wisconsin-Madison}, note = {Submitted (12/90) to the 1991 International Joint Conference on Artificial Intelligence}, number = {988}, title = {Case-Based Reasoning with Noisy Case Boundaries: An Application in Molecular Biology}, year = {1990} } @inproceedings{Shav91, author = {Jude Shavlik}, address = {Washington, DC}, booktitle = {Proceedings of the DARPA Cased-Based Reasoning Workshop}, pages = {327--338}, title = {Finding Genes by Case-Based Reasoning in the Presence of Noisy Case Boundaries}, year = {1991} } @inproceedings{Simo87, author = {I. Simon}, booktitle = {Proc.\ {LITP} Spring School on Theoretical Computer Science}, pages = {79--92}, series = {Lecture Notes in Computer Science}, title = {Sequence comparison: some theory and some practice}, volume = {377}, year = {1987} } @book{SK83, author = {D. Sankoff and J. B. Kruskal}, address = {Reading, {MA}}, publisher = {Addison-Wesley}, title = {Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison}, year = {1983} } @article{SKH93, author = {D. Seto and B.F. Koop and L. Hood}, journal = {Genomics}, pages = {673--676}, title = {An Experimentally Derived Data Set Constructed for Testing Large-Scale {DNA} Sequence Assembly Algorithms}, volume = {15}, year = {1993} } @article{SM82, author = {Staden, R. and A. Mc{L}achan}, journal = nar, pages = {141--156}, title = {Codon Preference and Its Use in Identifying Protein Coding Regions in Long {DNA} Sequences}, volume = {10}, year = {1982} } @article{SM86, author = {E. Sobel and H. M. Martinez}, journal = nar, number = {1}, pages = {363--374}, title = {A Multiple Sequence Alignment Program}, volume = {14}, year = {1986} } @book{SM97, author = {J. C. Setubal and J. Meidanis}, note = {ISBN: 0-534-95262-3}, publisher = {PWS Publishing Company}, title = {Introduction to Computational Molecular Biology}, year = {1997} } @Book{SM2001j, author = {J. C. Setubal and J. Meidanis}, title = {Introduction to Computational Molecular Biology}, publisher = {Brooks/Cole Publishing Company}, year = 2001, note = {ISBN: 4-320-05580-3. In Japanese} } @article{Sta79, author = {R. Staden}, journal = nar, pages = {2601--2610}, title = {A Strategy of {DNA} Sequencing Employing Computer Programs}, volume = {6}, year = {1979} } @article{Stad80, author = {Staden, R.}, journal = nar, number = {16}, pages = {3673--3694}, title = {A new computer method for the storage and manipulation of {DNA} gel reading data}, volume = {8}, year = {1980} } @article{Stad82, author = {Staden, R.}, journal = nar, pages = {4731--4751}, title = {Automation of the Computer Handling of Gel Reading Data Produced by the Shotgun Method of {DNA} Sequencing}, volume = {10}, year = {1982} } @article{Stad91, author = {S. Dean and Staden, R.}, journal = nar, number = {14}, pages = {3907--3911}, title = {A Sequence Assembly and Editing Program for Efficient Management of Large Projects}, volume = {19}, year = {1991} } @techreport{Step92, author = {G. A. Stephen}, address = {Dean Street, Bangor, Gwynedd, UK LL57 1UT}, institution = {School of Electronic Engineering Science, University College of North Wales}, number = {{TR}-92-gas-01}, title = {String Search}, year = {1992} } @article{Stra83, author = {V. Strassen}, journal = {SIAM J. on Computing}, month = Feb, number = {1}, pages = {1--27}, title = {The Computational Complexity of Continued Fractions}, volume = {12}, year = {1983} } @misc{Strings, note = {Strings abbreviate journal names, book names, etc.}, x = "************************************************************" } @article{SW81, author = {T. F. Smith and M. S. Waterman}, journal = jmb, pages = {195--197}, title = {Identification of Common Molecular Subsequences}, volume = {147}, year = {1981} } @article{SWB85, author = {T. F. Smith and M. S. Waterman and C. Burks}, journal = nar, number = {2}, pages = {645--656}, title = {The Statistical Distribution of Nucleic Acid Similarities}, volume = {13}, year = {1985} } @article{SWF81, author = {T. F. Smith and M. S. Waterman and W. M. Fitch}, journal = {J. Molec. Evol.}, pages = {38--46}, title = {Comparative Biosequence Metrics}, volume = {18}, year = {1981} } @article{SY82, author = {J. M. Steele and A. C. Yao}, journal = {J. of Algorithms}, pages = {1--8}, title = {Lower bounds for algebraic decision trees}, volume = {3}, year = {1982} } @book{Tama91, author = {R. Tamarin}, edition = {3rd}, publisher = {Wm. C. Brown Publishers}, title = {Principles of Genetics}, year = {1991} } @book{Tarj83, author = {Robert Endre Tarjan}, publisher = siam, title = {Data Structures and Network Algorithms}, year = {1983} } @incollection{Tay90, author = {W. Taylor}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {456--474}, publisher = {Academic Press}, series = me, title = {Hierarchical Methods to Align Large Numbers of Biological Sequences}, volume = {183}, year = {1990} } @incollection{TBDS90, author = {David C. Torney and Christian Burks and Daniel Davidson and Karl M. Sirotkin}, booktitle = {Computers and {DNA}}, editor = {George I. Bell and Thomas M. Marr}, pages = {109--125}, publisher = {Addison-Wesley}, title = {Computation of {$d^2$}: A Measure of Sequence Dissimilarity}, year = {1990} } @article{TH79, author = {Trotter, Jr., William T. and Frank Harary}, journal = {J. Graph Theory}, pages = {205--211}, title = {On Double and Multiple Interval Graphs}, volume = {3}, year = {1979} } @article{Turn89, author = {Jonathan S. Turner}, journal = {Information and Computation}, pages = {1--20}, title = {Approximation algorithms for the shortest common superstring problem}, volume = {83}, year = {1989} } @unpublished{UM91, author = {E. Uberbacher and R. Mural}, note = {Manuscript}, title = {Locating Protein Coding Regions in Human {DNA} Sequences Using a Neural Network -- Multiple Sensor Approach}, year = {1991} } @article{Vali84, author = {L. G. Valiant}, journal = cacm, pages = {1134--1142}, title = {A theory of the learnable}, volume = {27}, year = {1984} } @Article{V+2003, author = {Vettore, A. L. and da Silva, F. R. and Kemper, E. L. and Souza, G. M. and da Silva, A. M. and Ferro, M. I. and Henrique-Silva, F. and Giglioti, E. A. and Lemos, M. V. and Coutinho, L. L. and Nobrega, M. P. and Carrer, H. and Franca, S. C. and Bacci Junior, M. and Goldman, M. H. and Gomes, S. L. and Nunes, L. R. and Camargo, L. E. and Siqueira, W. J. and Van Sluys, M. A. and Thiemann, O. H. and Kuramae, E. E. and Santelli, R. V. and Marino, C. L. and Targon, M. L. and Ferro, J. A. and Silveira, H. C. and Marini, D. C. and Lemos, E. G. and Monteiro-Vitorello, C. B. and Tambor, J. H. and Carraro, D. M. and Roberto, P. G. and Martins, V. G. and Goldman, G. H. and de Oliveira, R. C. and Truffi, D. and Colombo, C. A. and Rossi, M. and de Araujo, P. G. and Sculaccio, S. A. and Angella, A. and Lima, M. M. and de Rosa Junior, V. E. and Siviero, F. and Coscrato, V. E. and Machado, M. A. and Grivet, L. and Di Mauro, S. M. and Nobrega, F. G. and Menck, C. F. and Braga, M. D. and Telles, G. P. and Cara, F. A. and Pedrosa, G. and Meidanis, J. and Arruda, P.}, title = {Analysis and functional annotation of an expressed sequence tag collection for tropical crop sugarcane}, journal = {Genome Research}, year = {2003}, OPTkey = {}, OPTvolume = {13}, OPTnumber = {12}, OPTpages = {2725--2735}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @article{vzG87, author = {von zur Gathen, J.}, journal = {SIAM J. Comput.}, month = {Oct}, number = {5}, pages = {930--945}, title = {Computing Powers in Parallel}, volume = {16}, year = {1987} } @inproceedings{vzGS86, author = {J. von zur Gathen and G. Seroussi}, address = {Santiago, Chile}, booktitle = {6th International Conference in Computer Science}, pages = {171--184}, title = {Boolean Circuits Versus Arithmetic Circuits}, year = {1986} } @book{Wake94, author = {John F. Wakerly}, edition = {Second}, note = {ISBN 0-13-211459-3}, publisher = {Prentice Hall}, title = {Digital Design Principles and Practices}, year = {1994} } @article{Wall84, author = {Wallace, R.B.}, journal = {Biotechnology Software}, pages = {6}, title = {{DNASTAR} - A Microcomputer-Based {DNA} Sequence Management System}, volume = {1}, year = {1984} } @inproceedings{Warn93, author = {T. Warnow}, booktitle = {Proc.\ 4th Symposium on Discrete Algorithms}, month = {jan}, title = {Tree compatibility and inferring evolutionary history}, year = {1993} } @book{Wate88, address = {Boca Raton, FL}, editor = {M. Waterman}, publisher = {CRC Press}, title = {Mathematical Methods for {DNA} Sequences}, year = {1988} } @article{WC53, author = {J. D. Watson and F. H. C. Crick}, journal = {Nature}, pages = {737--738}, title = {Molecular Structure of Nucleic Acids -- A Structure for Deoxyribose Nucleic Acid}, volume = {171}, year = {1953} } @article{WG86, author = {M. S. Waterman and J. R. Griggs}, journal = {Bull. Math. Biol.}, number = {2}, pages = {189--195}, title = {Interval Graphs and Maps of {DNA}}, volume = {48}, year = {1986} } @incollection{WJ90, author = {M. Waterman and R. Jones}, booktitle = molevol, editor = {Russell F. Doolittle}, pages = {221--237}, publisher = {Academic Press}, series = me, title = {Consensus Methods for {DNA} and Protein Sequence Alignment}, volume = {183}, year = {1990} } @article{WL83, author = {W. Wilbur and D. Lipman}, journal = pnas, pages = {726--730}, title = {Rapid Similarity Searches of Nucleic Acid and Protein Data Banks}, volume = {80}, year = {1983} } @book{Zehn70, author = {Peter W. Zehna}, address = {Boston}, publisher = {Allyn and Bacon}, title = {Probability Distributions and Statistics}, year = {1970} }