Selected (Mostly Recent) Publications
Gusfield

Books:

New-ish papers related to computation in population genomics

1. Association Mapping for Compound Heterozygous Traits Using Phenotypic Distance and Integer Programming
   Dan Gusfield and Rasmus Nielsen
   Proceedings of 2015 WABI conference
   
   

   Papers on (Multi-State) Perfect Phylogeny

2. Minimum Average-Distance Clique Trees.
   Shou-Jun Xu, Rob Gysel, Dan Gusfield.
   SIAM J. DISCRETE MATH. 2015 Society for Industrial and Applied Mathematics
   Vol. 29, No. 3, pp. 1706 - 1734
   
   
3. Triangulation heuristics for maximum character compatibility.
   Rob Gysel, Dan Gusfield, Kristian Stevens
   ICCABS 2013: 1-2 (This won the best paper award for the conference, but we only published the abstract in the proceedings. The journal version is still in preparation).
   
   
4. Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs.
   Rob Gysel, Kristian Stevens, Dan Gusfield.
   WABI 2012: 93-105
   
   
5. Constructing Perfect Phylogenies and Proper Triangulations for Three-State Characters
   Rob Gysel, Fumei Lam and Dan Gusfield.
   Proceedings of WABI 2011, Springer LNCS
   Journal Version: Algorithms for Molecular Biology 7: 26 (2012)
   
   
6. Reducing Multi-State to Binary Perfect Phylogeny with Applications to Missing, Removable, Inserted and Deleted Data.
   Kristian Stevens and Dan Gusfield
   Proceedings of WABI 2010, Springer LNCS Vol. 6293 2010, p. 274-287
   
   
7. Extensions and Improvements to the Chordal Graph Approach to the Multi-state Perfect Phylogeny Problem
   R. Gysel and D. Gusfield
   In Proceedings of the ISBRA Conference, 2010, Springer LNBI Vol. 6054, p. 52-60.
   
   
8. The Three-state Perfect Phylogeny Problem Reduces to 2-SAT.
   D. Gusfield and Y. Wu
   Communicationsand Information Systems, Special Issue Dedicated to Michael Waterman,
   Volume 9, No. 4, 2009. Pages 195-301
   
   
9. Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters
   Fumie Lam, D. Gusfield, S. Sridhar
   SIAM J. on Discrete Math. Vol. 25, No. 3, pp. 1144-1175
   
   This an expanded version of the WABI 2009 conference paper presented September 12, 2009.
   
   The main result of the paper is that there is a three-state perfect phylogeny (or in other terms, the data is compatible with a three-state tree) if and only if there is one for every subset of three characters. This generalizes the binary case where the classical four-gametes condition says that there is a binary perfect phylogeny in binary data if and only if there is one for every pair of characters. The paper also shows that there is a set of four subpatterns, each with three characters and five taxa, such that any three-state data that does not have a three-state perfect phylogeny must contain one of those four subpatterns. This generalizes the four-gametes condition which shows that when a pair of characters does not have a binary perfect phylogeny (is not compatible) the subpattern of all four binary combinations must appear in that pair of characters. The techniques are based on the chordal graph view of perfect phylogeny.
   
   
10. The Multi-State Perfect Phylogeny Problem with Missing and Removable Data; Solutions via Integer Linear Programming and Chordal Graph Theory
    Dan Gusfield
    In Proceedings of the 2009 RECOMB Conference, May 2009.
    
    Expanded journal version (with complete proofs)
    J. of Computational Biology, Vol. 17, no. 3, 2010, p. 383-399
    
    For software related to this paper see Software
    
    For powerpoint slides related to this paper see Recent Talks
    
    
    

    Papers on Phylogenetic Networks and ARGs with Recombination

11. A Resolution of the Static Formulation Question for the Problem of Computing the History Bound. TCBB, Volume 14, 2017, pages 404-417 ,
    Julia Matsieva, Steven Kelk, Celine Scornavacca, Chris Whidden, and Dan Gusfield
    
    
12. Persistent Phylogeny: A Galled-Tree and Integer-Linear Programming Approach.
    Dan Gusfield.
    2015 ACM Conference on Bioinformatics, Computational Biology and Health Informatics.
    
    
13. A Decomposition Theory for Phylogenetic Networks and Incompatible Characters
    Dan Gusfield, Vikas Bansal, Vineet Bafna, Yun S. Song
    Journal of Computational Biology Dec 2007, Vol. 14, No. 10: 1247-1272.
    This is a large expansion of the RECOMB 2005 conference paper listed below. It solves the major open question from that conference paper and extends the earlier results.
    
    
14. Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations
    Yun S. Song, Zhihong Ding, Dan Gusfield, Charles H. Langley, Yufeng Wu
    Journal of Computational Biology Dec 2007, Vol. 14, No. 10: 1273-1286
    This is the extended journal version of the RECOMB 2006 conference paper listed below.
    
    
15. A new recombination lower bound and the minimum perfect phylogenetic forest problem
    Y. Wu and D. Gusfield
    LNCS, vol. 4598, Proceedings of the 13'th Annual International Conference on Combinatorics and Computing, 2007, p. 16-26
    The Journal version is in Journal of Combinatorial Optimization, Vol 16, 2008
    
    
16. Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants
    Y. Wu and D. Gusfield
    LNCS, vol. 4580, Proceedings of the 18'th Annual Symposium on Combinatorial Pattern Matching, 2007, p. 150-161
    
    
17. An efficiently-computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study
    link to Science Direct for the final journal manuscript
    D. Gusfield, D. Hickerson, S. Eddhu
    Discrete Applied Mathematics, Special issue on Computational Biology, Vol. 155, pg. 806-830, 2007
    
    preprint in pdf
    
    
18. Efficient Computation of Minimum Recombination with Genotypes (not Haplotypes) (pdf)
    Y.Wu and D. Gusfield
    In Proceedings of The CSB Conference, Stanford CA., August 2006.
    The journal version appeared in J. Bioinformatics and Computational Biology, Vol. 5 No. 2(a), 2007, p. 181-200
    
    
19. Algorithms to distinguish the role of gene-conversion from single-crossover recombination in the derivations of SNP sequences in populations (pdf)
    Y.S. Song, Z. Ding, D. Gusfield, C. Langley, Y. Wu
    In Proceedings of RECOMB 2006.
    ps version
    The Journal version is in Journal of Computational Biology, Vol. 14, 2007
    
    
20. Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution
    Yun S. Song, Yufeng Wu and Dan Gusfield
    Proceedings of ISMB 2005, published as a special issue of Bioinformatics
    
    For the associated software
    HapBound and SHRUB
    
    
21. On the Full-Decomposition Optimality Conjecture for Phylogenetic Networks (pdf)
    
    D. Gusfield
    UCD Technical Report, Jan. 2005
    
    
22. A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters (pdf)
    click here for postscript version
    D. Gusfield and V. Bansal
    Proceedings of RECOMB 2005, May 2005
    
    
23. Optimal, Efficient Reconstruction of Root-Unknown Phylogenetic Networks with Constrained and Structured Recombination (pdf)
    click here for postscript version
    Technical Report UCDavis CSE-2004-31
    D. Gusfield
    November 25, 2004,
    Journal version appears in J. Computer and Systems Sciences, 2005 Special issue on Computational Biology.
    Vol. 70 (2005) p. 381-398
    
    
24. A fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters (pdf)
    click here for postscript version
    Technical Report UCDavis CSE-2004-32
    D. Gusfield
    October 14, 2004,
    
    
25. Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination (pdf)
    Click here for Postscript
    D. Gusfield, S. Eddhu, C. Langley
    Journal of Bioinformatics and Computational Biology, Vol. 2 no. 1 (2004) p. 173-213
    Special Issue on the 2003 IEEE CSB Bioinformatics Conference.
    
    This is a much expanded journal version of the conference paper listed next.
    
    
26. Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination (pdf)
    Click here for Postscript
    D. Gusfield, S. Eddhu, C. Langley
    Proceedings of the 2003 IEEE CSB Bioinformatics Conference. This won the best-paper award.
    Thank you Hewlett Packard for donating the prize money.
    
    
27. The Fine Structure of Galls in Phylogenetic Networks (pdf)
    D. Gusfield, S. Eddhu, C. Langley
    INFORMS J. of Computing Special Issue on Computational Biology (2004).
    
    

    Papers on Haplotype Inference

28. Analytical and Algorithmic Methods for Haplotype Frequency Inference: What do they tell us?
    S. Orzack, D. Gusfield, L. Subrahmanyan, L. Essioux, S. Lissarrague
    in Bioinformatics Algorithms: Techniques and Applications, I. Mandoiu and A. Zelikovsky (eds.), Wiley 2008, p. 373-394
    
    
29. Algorithms for Imperfect Phylogeny Haplotyping with a Single Homoplasy or Recombination Event (pdf),
    Y. S. Song, Y. Wu and Gusfield
    Proceedings of WABI 2005, October 2005, Lecture Notes in Bioinformatics
    In this paper we look at extensions of the PPH problem (see below) to situations where the underlying haplotypes that form the genotypes do not evolve on a perfect phylogeny, but rather evolve either on a tree with one homoplasy event (a recurrent or back mutation) or on a network with one recombination event. Using one emprically-justified assumption, we present a polynomial time algorithm for the first problem (the case of one homoplasy event) and an exponential-time algorithm for the second problem. We have subsequently developed a polynomial-time algorithm for the second problem as well.
    
    
30. A Linear-Time Algorithm for Perfect Phylogeny Haplotyping (pdf)
    Z. Ding, V. Filkov, D. Gusfield
    This is the expanded, full journal version of the RECOMB conference paper below.
    Journal of Computational Biology, Vol. 13, No. 2, pg. 522-553, 2006
    
    
31. A Linear-Time Algorithm for Perfect Phylogeny Haplotyping (pdf)
    Z. Ding, V. Filkov, D. Gusfield
    Proceedings of RECOMB 2005, May 2005
    
    click here for postscript version
    This paper solves the open question of whether the Perfect Phylogeny Haplotyping (PPH) Problem can be solved in linear time. The method presented is simple enough for easy implementation, and our implementation is on the web.
    
    
32. Haplotype Inference (pdf)
    D. Gusfield and S.H. Orzack
    In CRC Handbook on Bioinformatics, 2006 (S. Aluru Editor), p. 18-1 18-25
    
    
33. A Note on Efficient Computation of Haplotypes via Perfect Phylogeny
    Vineet Bafna, Dan Gusfield, Sridhar Hannenhalli, Shibu Yooseph
    Journal of Computational Biology, Vol. 11, no. 5, 2004, p. 858-866
    
    This paper shows that two prior methods for the PPH problem are unlikely to be implementable in linear time. It also shows that the problem of finding a PPH solution that minimizes the number of distinct haplotypes used (over all PPH solutions) is NP-hard.
    
    
34. An Overview of Combinatorial Methods for Haplotype Inference (pdf)
    In Computational Methods for SNPs and Haplotype Inference, S. Istrail, M. W aterman, and A. Clark (eds). Lecture Notes in Computer Science, vol. 2983, Springer, p. 9-25, 2004.
    
    click here for postscript version
    (2004) A survey of combinatorial algorithms and software
    for haplotype inference developed at UC Davis.
    D. Gusfield
    
    
35. Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers (pdf)
    
    click here for postscript version
    R.H. Chung and D. Gusfield
    Proceedings of the 2003 Cocoon Conference July 2003
    Link to the proceedings
    This reports on the performance of three perfect phylogeny haplotyping programs, and on two interesting phenomena observed when solving the perfect phylogeny haplotyping problem on simulated data.
    
    
36. Haplotyping by Pure Parsimony (pdf)
    click here for postscript version
    Technical Report UCDavis CSE-2003-2
    D. Gusfield
    January 23, 2003,
    Final version in The Proceedings of the 2003 Combinatorial Pattern Matching Conference, June 2003
    Link to conference proceedings
    
    The Pure Parsimony problem for Haplotype Inference is to find the smallest set of binary strings that can generate an input set of genotypes. The Pure Parsimony problem is NP-hard, and no paper has previously shown how an optimal Pure-Parsimony solution can be computed efficiently for problem instances of the size of current biological interest. In this paper, we show how to formulate the Pure-Parsimony problem as an integer linear program; we explain how to improve the practicality of the integer programming formulation; and we present the results of extensive experimentation we have done to show the time and memory practicality of the method, and to compare its accuracy against solutions found by the widely used general haplotyping program PHASE. The results are that the Pure Parsimony problem can be solved efficiently in practice for a wide range of problem instances of current interest in biology. Both the time needed for a solution, and the accuracy of the solution, depend on the level of recombination in the input strings. The speed of the solution improves with increasing recombination, but the accuracy of the solution decreases with increasing recombination.
    
    
37. Haplotyping as Perfect Phylogeny: A direct approach (pdf).
    Haplotyping as Perfect Phylogeny: A direct approach (postscript)
    Technical Report UCDavis CSE-2002-21
    V. Bafna, D. Gusfield, G. Lancia, S. Yooseph
    July 17, 2002.
    An augmented version has appeared in Journal of Computational Biology, Vol. 10 No. 3 (2003) p. 323-340.
    
    This develops a more direct, self-contained method (than the first paper in the area: "Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions") determining whether unphased genotype data can be explained by haplotypes that fit a perfect phylogeny. It gives a more intuitive and algorithmicly simpler way to create the representation of all such solutions. An implementation of this method is available at:
    DPPH .
    
    
38. Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions. (pdf)
    Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions (postscript)
    D. Gusfield
    Appeared in RECOMB 2002, April 2002.
    This paper develops an almost-linear-time algorithm to determine if unphased genotype data can be explained by haplotype pairs which fit a rooted perfect phylogeny. If there is such an explanation, then the algorithm, in linear additional time, determines if the solution is unique, and if not, produces a representation of all the solutions. The method is based on reducing the haplotype problem to a problem of graph realization. We use this reduction to graph realization, in the software package GPPH (previously called PPH). However, in GPPH, we use a somewhat slower way to solve the graph realization problem than is described in the paper.
    
    Errata for: Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions (pdf)
    Errata for: Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions (postscript)
    
    
    
39. Perfect Phylogeny Haplotyper: Haplotype Inferral Using a Tree Model (pdf)
    Perfect Phylogeny Haplotyper: Haplotype Inferral Using a Tree Model (Postscript)
    R.H. Chung and D. Gusfield.
    This gives a short description of the program PPH (now called GPPH), which implements the solution method discussed in the prior paper and Errata.
    Bioinformatics, Vol. 19, No. 6, pp. 780-781, 2003.
    
    
40. Inference of Haplotypes in Samples of Diploid Populations: Complexity and Algorithms.(pdf)
    Inference of Haplotypes in Samples of Diploid Populations: Complexity and Algorithms (postscript)
    D. Gusfield
    In Journal of Computational Biology, Vol. 8, No. 3, 2001 p. 305-323
    
    
41. The absolute and relative accuracy of haplotype inferral methods and a consensus approach to haplotype inferral. S. H. Orzack, D. Gusfield, V.P. Stanton.
    Abstract in 51'th Annual Meeting of the American Society of Human Genetics, Fall 2001.
    The full, much expanded paper (in Genetics, listed next) details how to modify Clark's well-known and widely used method of haplotype inferral to greatly boost its accuracy, making it nearly competitive in accuracy with PHASE, and vastly faster. This paper is almost unique in the literature in that it compares the accuracy of the methods to laboratory determined haplotype data - determined by one of the authors. It is the joint collaboration of a computer scientist, a geneticist and molecular biologists.
    
    
42. Analysis and Exploration of the Use of Rule-Based Algorithms and Consensus Methods for the Inferral of Haplotypes
    Genetics, Vol. 165, 915-928, October 2003
    Steven Hecht Orzack, Daniel Gusfield, Jeffrey Olson, Steven Nesbitt, Lakshman Subrahmanyanc, and Vincent P. Stanton, Jr.

    Papers on Algorithms for RNA Folding

43. A Sparsified Four-Russians Algorithm for RNA Folding.
    Yelena Frid, Dan Gusfield:
    2015 Workshop on Algorithms in Bioinformatics (WABI).
    
    
44. Faster Algorithms for RNA-Folding Using the Four-Russians Method
    Balaji Venkatachalam, Dan Gusfield, and Yelena Frid
    Proceedings of The WABI Conference, 2013. Springer LNCS
    pages 126-140
    Journal Version: Algorithms for Molecular Biology 9: 5 (2014)
    
    
45. Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method
    Yelena Frid and Dan Gusfield
    Proceedings of 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012.
    Springer LNCS Vol. 7402
    pages 176-187
    
    
46. Worst-Case and Practical Speedup for the RNA co-folding Problem using the 4-Russians Idea.
    Yelena Frid and Dan Gusfield
    Proceedings of WABI 2010, Springer LNCS Vol. 6293, 2010, p. 1-12.
    
    
47. A simple, practical and complete O(n^3/ log n)-time Algorithm for RNA folding using the Four-Russians Speedup
    Yelena Frid, D. Gusfield
    
    Presented at the WABI 2009 conference, September 13, 2009
    Expanded and corrected Journal Version: in Algorithms for Molecular Biology 2010, 5:13
    
    

    Other Recent Papers and Proceedings in Computational Biology and Bioinformatics

48. Untangling Tanglegrams: Comparing Trees by Their Drawings
    Venkatachalam, B; Apple, J; St John, K; Gusfield, D,
    In Proceedings of BIOINFORMATICS RESEARCH AND APPLICATIONS, 5542: 88-99
    MAY 13-16, 2009
    
    Journal Version: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 7, 2010, p. 588-597
    
    
49. Integer Programming Formulations and Computations Solving Phylogenetic and Population Genetic Problems with Missing or Genotypic Data (pdf)
    D. Gusfield and Y. Frid and D. Brown
    LNCS, vol. 4598, Proceedings of the 13'th Annual International Conference on Combinatorics and Computing, 2007, p. 51-64
    
    
50. Linear-Time Algorithms for Finding and Representing all Tandem Repeats in a String (pdf)
    D. Gusfield and J. Stoye
    JCSS, vol. 69, 2004, p. 525-546
    We show how to decorate a suffix tree for a string with the endpoints of all the distinct substrings of the string that are tandem repeats. The algorithm runs in linear-time as a function of the length of the string. Of course, such an algorithmic result would not be possible without the remarkable mathematical result, proven by A. Frankel and J. Simpson in 1998, that there can only be a linear number of distinct substrings that are tandem repeats. The actual bound is 2n, for a string of length n. After the suffix tree is decorated, almost all imaginable questions about the tandem repeats or tandem arrays (how many occurrences there are, where they occurr, their average length, the maximum and minimum lengths from given positions etc.) that were previously studied individually, can be answered efficiently using this decorated suffix tree.
    
    
51. RECOMB 2004, Proceedings of the Eighth Annual International Conference on Computational Molecular Biology
    ACM Press
    D. Gusfield (Program Chair), P. Bourne, S. Istrail, P. Pevzner, M. Waterman (editors)
    
    
52. Algorithms in Bioinformatics
    Proceedings of the Second International Workshop on Algorithms in Bioinformatics, WABI 2002, Rome, Italy, September 2002
    Springer Lecture Notes in Computer Science Vol. 2452, 554 pages
    R. Guigo and D. Gusfield (editors)
    
    
53. String Barcoding: Uncovering Optimal Virus Signatures (pdf)
    S. Rash and D. Gusfield, Appeared in RECOMB 2002, April 2002
    
    
54. On the Complexity of Fundamental Computational Problems in Pedigree Analysis (pdf)
    On the Complexity of Fundamental Computational Problems in Pedigree Analysis (postscript)
    A. Piccolboni and Dan Gusfield
    An improved version has appeared in Journal of Computational Biology, Vol 10, No. 5, 2003, p. 763-774.
    
    
55. Partition-distance: A problem and class of perfect graphs arising in clustering (pdf),
    Partition-distance: A problem and class of perfect graphs arising in clustering (postscript),
    Dan Gusfield
    Information Processing Letters, Volume 82, Issue 3, 16 May 2002, Pages 159-164
    
    
56. Simple and flexible detection of contiguous repeats using a suffix tree (pdf) ,
    Simple and flexible detection of contiguous repeats using a suffix tree (postscript) ,
    Jens Stoye and Dan Gusfield
    Theoretical Computer Science, Volume 270, Issues 1-2, 6 January 2002, Pages 843-856
    
    

    Other Recent Papers

57. The structure and complexity of sports elimination numbers (pdf)
    The structure and complexity of sports elimination numbers (postscript)
    Dan Gusfield and Chip Martel,
    In Algorithmica (2002) 32, pages 73-86

Hard to Find Older Papers

1. Efficient Algorithms for Inferring Evolutionary Trees (pdf)
   Efficient Algorithms for Inferring Evolutionary Trees (ps)
   D. Gusfield
   
   I get many requests for this paper from people who can't find it in their libraries. It is my most cited journal publication. It was also my first submitted paper in computational biology, submitted around 1985, and rejected (I won't reveal the journal). It was published in Networks, Vol. 21 (1991) p. 19-28. Networks is no longer a major journal (judging by the libraries that don't receive it, and I guess even by 1991, it was not widely received.). So I am posting the version of it that I found in my files (after much searching). It may not be absolutely identical to the published paper, but it has all the results. The paper has three results: How to find a perfect phylogeny (if there is one) in linear time; a lower bound proof that every entry in the data has to be examined; how to solve the tree compatibility problem in linear time. The first result is also obtained in a somewhat nicer way in my book Algorithms on Strings, Trees and Sequences.
   
   
2. A little knowledge goes a long way: Faster detection of compromised data in 2-D tables(pdf)
   D. Gusfield
   
   This paper is buried in the Proceedings of the 1990 Oakland conference on Research in Security and Privacy. I don't think anyone knows it is there - I should have published it in a journal.
   
   The paper considers the following problem Statistical Data Security: In a 2-D table of non-negative numbers, say n by n, where all the row totals and column totals are known, but only some of the n^2 cell values are known, one wants to determine, for each cell whose value is not known, what is the maximum possible value that the cell could take on. That is, if cell (i,j) has an unknown value, what is the maximum value for cell (i,j) so that there is a setting of all the other unknown (non-negative) values that makes all the rows and columns sum to their correct, fixed values? In this paper I show that no matter how many cell values are unknown, one needs to solve this problem only 2n-1 times. More specifically, I give an algorithm that selects at most 2n-1 of the cells, so that after the maximum value is determined for each of those 2n-1 cells, the maximum value can be obtained for each of the remaining unknown values by doing a single lookup in a table built during the solving of the first 2n-1 problems. So, the maximum value can be determined in constant time for each of the remaining cells. The total time for the algorithm is the time needed for 4n-2 network flow computations in a directed graph of 2n nodes.
   
   
3. New Uses for Uniform Lifted Alignments (pdf)
   D. Gusfield and L. Wang.
   In Mathematical Support for Molecular Biology.
   DIMACS Series on Discrete Math and Theoretical Computer Science, VOL. 47, p. 33-52 (1999)
   
   This paper is obscure due to a terrible choice of titles. It should have been called something like:
   
   How to Compute Evolutionary History Really Badly, and Why I Want to.
   
   The paper uses approximation algorithms in a way that is backwards from what they were designed for, in order to establish bounds on the accuracy of certain computations, rather than trying to find good solutions. The key to doing this is to make an approximation algorithm as inaccurate as possible, while still producing a solution that falls within the worst-case approximation bound. One reviewer of this paper wrote ``This is the dumbest idea I have heard in a long time". We use this approach to try to show that a particular tree alignment of RNA sequences that David Sankoff and Robert Cedergren constructed in 1983 is close to the optimal alignment (under a given objective function). A simple analysis showed that the cost of their alignment is no more than 62% larger than the optimal. In this paper we show that its cost is no more than 16.57% larger than the optimal. I think this idea of using an approximation algorithm backwards can be applied in other problems, but I have never seen the idea picked up by anyone else.
   
   
4. Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds
   Bulletin of Mathematical Biology, Vol. 55, p. 141-154, 1993
   
   A pre-publication version with all the main results, but a bit more raw than the published journal version.
   
   This was the first use of a bounded approximation algorithm in computational biology. The particular multiple alignment method developed in the paper was only for the purpose of being able to prove a guaranteed bound on the error, and hence the result in the paper is mainly theoretical. However, it has been reported that the actual alignments are useful in some applications.
   
   A historical trivia note: This is the first (oldest) paper PubMed indexed using the search term Computational Biology. PubMed query
   
   
5. Parametric and Inverse Parametric Sequence Alignment with XPARAL
   D. Gusfield and P. Stelling
   
   Methods in Enzymology, Vol. 266, 1996
   
   

A full list of journal and conference publications as of April 2012