| 1. |
Felsenstein, J. (2004) Inferring Phylogenies. Sinauer Associates, Sunderland, MA.
|
| |
| 2. |
Gusfield, D. (1997) Algorithms on strings, trees, and sequences. Computer Science and Computational Biology. Cambridge University Press, Cambridge, MA.
|
| |
| 3. |
Page, R. D. M., Holmes, E. C., eds. (1998) Molecular Evolution: A Phylogenetic Approach. Blackwell Science, Ames, IA.
|
| |
| 4. |
Semple, C., Steel, M. (2003) Phylogenetics. Oxford University Press, New York.
|
| |
| 5. |
Smith, V. S. (2001) Avian louse phylogeny (phthiraptera: Ischnocera): a cladistic study based on morphology. Zool J Linnean Soc 132, 81–144.
|
| |
| 6. |
Bodlaender, H. L., Fellows, M. R., Warnow, T. (1992) Two strikes against perfect phy-logeny. In Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP), Springer-Ver-lag, New York.
|
| |
| 7. |
Steel, M. (1992) The complexity of reconstructing trees from qualitative characters and subtrees. J Class 9, 91–116.
|
| |
| 8. |
Gusfield, D. (2002) Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In Proceedings of the Sixth Annual International Conference on Computational Molecular Biology (RECOMB), ACM Press, New York.
|
| |
| 9. |
McMorris, F. R., Warnow, T. J., Wimer T. (1993) Triangulating vertex colored graphs. In Proceedings of the Fourth Symposium on Discrete Algorithms (SODA), SIAM Press, Austin, Texas.
|
| |
| 10. |
Agarwala, R., Fernández-Baca, D. (1996) Simple algorithms for perfect phylogeny and triangulating colored graphs. Int J Found Comput Sci 7, 11–21.
|
| |
| 11. |
Bodlaender, H. L., Fellows, M. R., Hallett, M. T., et al. (2000) The hardness of perfect phylogeny, feasible register assignment
and other problems on thin colored graphs. Theoret Comput Sci 244, 167–188.
|
| |
| 12. |
Agarwala, R., Fernández-Baca, D. (1994) A polynomial-time algorithm for the perfect phylogeny problem when the number of character
states is fixed. SIAM J Comput 23, 1216–1224.
|
| |
| 13. |
Kannan, S., Warnow, T. (1997) A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM J Comput 26, 1749–1763.
|
| |
| 14. |
Dress, A., Steel, M. (1992) Convex tree realizations of partitions. Appl Math Lett 5, 3–6.
|
| |
| 15. |
Kannan, S., Warnow, T. (1994) Inferring evolutionary history from dna sequences. SIAM J Comput. 23, 713–737.
|
| |
| 16. |
Estabrook, G. F., Johnson Jr., C. S., McMorris, F. R. (1975) An idealized concept of the true cladistic character. Math Biosci 23, 263–272.
|
| |
| 17. |
Meacham, C. A. (1983) Theoretical and computational considerations of the compatibility of qualitative taxonomic characters.
Nato ASI series, volume G1 on Numercal Taxonomy.
|
| |
| 18. |
Gusfield, D. (1991) Efficient algorithms for inferring evolutionary trees. Networks 21, 19–28.
|
| |
| 19. |
Fernández-Baca, D., Lagergren, J. (2003) A polynomial-time algorithm for near-perfect phylogeny. SIAM J Comput 32, 1115–1127.
|
| |
| 20. |
Goldberg, L. A., Goldberg, P. W., Phillips, C., et al. (1996) Minimizing phylogenetic number to find good evolutionary trees.
Dis Appl Math 71, 111–136.
|
| |
| 21. |
Moran, S., Snir, S. (2005) Convex recolorings of phylogenetic trees: definitions, hardness results and algorithms. In Proceedings of the Ninth Workshop on Algorithms and Data Structures (WADS), Springer-Verlag, New York.
|
| |
| 22. |
Blelloch, G. E., Dhamdhere, K., Halperin, E., et al. (2006) Fixed-parameter tractability of binary near-perfect phylogenetic
tree reconstruction. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Springer-Verlag, New York.
|
| |
| 23. |
Sridhar, S., Dhamdhere, K., Blelloch, G. E., et al. (2005) FPT algorithms for binary near-perfect phylogenetic trees. Computer
Science Department, Carnegie Mellon University. Technical Report CMU-CS-05–181.
|
| |
| 24. |
Wernicke, S., Alber, J., Gramm, J., et al. (2004) Avoiding forbidden submatrices by row deletions. In Proceedings of the 31st Annual Conference on Current Trends in Theory and Practice of Informatics (SOF-SEM), Springer-Verlag, New York.
|
| |
| 25. |
DasGupta, B., He, X., Jiang, T., et al. (1998) Handbook of Combinatorial Optimization. Kluwer Academic Publishers, Philadelphia.
|
| |
| 26. |
Gogarten, J. P., Doolittle, W. F., Lawrence J. G. (2002) Prokaryotic evolution in light of gene transfer. Mol Biol Evol 19, 2226– 2238.
|
| |
| 27. |
DasGupta, B., He, X., Jiang, T., et al. (2000) On computing the nearest neighbor interchange distance. In Discrete Mathematical Problems with Medical Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Providence, RI.
|
| |
| 28. |
Hein, J., Jiang, T., Wang, L., et al. (1996) On the complexity of comparing evolutionary trees. Disc Appl Math 71, 153–169.
|
| |
| 29. |
Allen, B. L., Steel, M. (2001) Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics. 5, 1–13.
|
| |
| 30. |
Fernau, H., Kaufmann, M., Poths, M. (2005) Comparing trees via crossing minimization. In Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science (FST-TCS), Springer-Verlag, New York.
|
| |
| 31. |
Sanderson, M. J., Purvis, A., Henze, C. (1998) Phylogenetic supertrees: Assembling the tree of life. Trends Ecol Evol 13, 105–109.
|
| |
| 32. |
Kluge, A. G. (1989) A concern for evidence and a phylogenetic hypothesis of relationships among epicrates (boidæ, serpents). Syst Zool 38, 7–25.
|
| |
| 33. |
Gordon, A. D. (1986) Consensus super-trees: the synthesis of rooted trees containing overlapping sets of labeled leaves. J Class 3, 31–39.
|
| |
| 34. |
Baum, B. R. (1992) Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining
gene trees. Taxon 41, 3–10.
|
| |
| 35. |
Doyle, J. (1992) Gene trees and species trees: molecular systematics as one- character taxonomy. Syst Botany 17, 144–163.
|
| |
| 36. |
Ragan, M. (1992) Phylogenetic inference based on matrix representation of trees. Mol Phylogenet Evol 1, 53–58.
|
| |
| 37. |
Bininda-Emonds, O., ed. (2004) Phylogenetic Supertrees. Kluwer Academic Publishers, Dordrecht.
|
| |
| 38. |
Aho, A. V., Sagiv, Y., Szymansk, T. G., et al. (1981) Inferring a tree from lowest common ancestors with an application to
the optimization of relational expressions. SIAM J Comput 10, 405–421.
|
| |
| 39. |
Steel, M. (August 2001) Personal communication. Open question posed at the Dagstuhl workshop 03311 on fixed-parameter algorithms.
|
| |
| 40. |
Bryant, D., Lagergren, J. (2006) Compatibility of unrooted trees is FPT. Theoret Comput Sci 351, 296–302.
|
| |
| 41. |
Gramm, J., Niedermeier, R. (2003) A fixed-parameter algorithm for Minimum Quartet Inconsistency. J Comp Syst Sci 67, 723–741.
|
| |
| 42. |
Amenta, N., Clarke, F., St. John, K. (2003) A linear-time majority tree algorithm. In Proceedings of the Third Workshop on Algorithms in Bioinformatics (WABI), Springer-Verlag, New York.
|
| |
| 43. |
Amir, A., Keselman, D. (1997) Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithm. SIAM J Comput 26, 1656–1669.
|
| |
| 44. |
Farach, M., Przytycka, T. M., Thorup, M. (1995) On the agreement of many trees. Inf Proc Lett 55, 297–301.
|
| |
| 45. |
Berry, V., Nicolas, F. (2006) Improved parametrized complexity of maximum agreement subtree and maximum compatible tree problems.
IEEE/ACM Trans Comput Biol Bioinform 3, 284–302.
|
| |
| 46. |
Tagle, D. A., Koop, B. F., Goodman, M., et al. (1988). Embryonic ε and γ globin genes of a prosimian primate (Galago crassicaudatus)
nucleotide and amino acid sequences, developmental regulation and phylogenetic footprints. J Mol Biol 203, 439–455.
|
| |
| 47. |
Blanchette, M., Schwikowski, B., Tompa, M. (2002) Algorithms for phylogenetic footprinting. J Comput Biol 9, 211–223.
|
| |
| 48. |
Ding, Z., Filkov, V., Gusfield, D. (2005) A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem. In
Proceedings of the Ninth Annual International Conference on Research in Computational Molecular Biology (RECOMB), Springer-Verlag, New York.
|
| |
| 49. |
Gramm, J., Nierhoff, T., Tantau, T., et al. (2007) Haplotyping with missing data via perfect path phylogenies. Discrete Appl Math 155, 788–805.
|
| |
| 50. |
Kimmel, G., Shamir, R. (2005) The incomplete perfect phylogeny haplotype problem. J Bioinformatics and Comput Biol 3, 359–384.
|
| |
| 51. |
Zhang, J., Rowe, W. L., Clark, A. G., et al. (2003) Genomewide distribution of high-frequency, completely mismatching snp
haplotype pairs observed to be common across human populations. Amer J Hum Genet 73, 1073–1081.
|
| |
| 52. |
Durbin, R., Eddy, S. S., Krogh, A., et al. (1998) Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge, MA.
|
| |
| 53. |
Chor, B., Tuller, T. (2005) Maximum likelihood of evolutionary trees: Hardness and approximation. Proceedings of the 13th International Conference on Intelligent Systems for Molecular Biology (ISBM). Bioin-formatics 21, 97–106.
|
| |
| 54. |
Chor, B., Tuller, T. (2005) Maximum likelihood of evolutionary trees: Hardness and approximation. In Proceedings of the Ninth Annual International Conference on Research in Computational Molecular Biology (RECOMB), Springer-Verlag, New York.
|
| |
| 55. |
Lander, E. S., Linton, M., Birren, B., et al. (2001) Initial sequencing and analysis of the human genome. Nature 409, 860–921.
|
| |
| 56. |
Salzberg, S. L., White, O., Peterson, J., et al. (2001) Microbial genes in the human genome: lateral transfer or gene loss.
Science 292, 1903–1906.
|
| |
| 57. |
Andersson, J. O., Doolittle, W. F., Nesbϕ, C. L. (2001) Are there bugs in our genome? Science 292, 1848–1850.
|
| |
| 58. |
Pérez-Moreno, B. P., Sanz, J. L., Sudre, J., et al. (1993). A theropod dinosaur from the lower cretaceous of southern France.
Revue de Paléobiologie 7, 173–188.
|
| |
| 59. |
Holtz T. R. Jr. (1994) The phylogenetic position of the Tyrannosauridae: implications for theropod systematics. J Paleontol 68, 1100–1117.
|
| |