Classified References on Computational Biology
R. C. T. Lee
OnBooks
On Classification ofProtein Folds
On EvolutionaryTrees
On Divide-and-Conquer
On GenomeRearrangement
OnLCS
On Miscellaneous
On Nearest Neighbor Search
On Pattern Discovery
On Physical Mapping
On ProteinStructure
On RNA Structures
On SequenceAlignment
On Sequence Assembly Problem
On Sorting byReversal
OnStringMatching
On Structure Alignment
On Superstrings
On Superstructures
On VisualDisplay
On NP-Complete Problems andApproximation Algorithms
On Sequence Assembly Problem
[CFM80] The k Best Spanning Arborescences of a Network, Camperini, P., Fratta, L. and Maffioli, F., Networks, Vol. 10, 1980, pp. 91-110.
[DS1991] A Sequence Assembly and Editing Program for Efficient Management of Large Projects, Dean, S. and Staden, R., Nucleic Acids Research, Vol. 19, 1991, pp. 3901-3917.
[GMSR79] Computer Problems for the Assembly of DNA Sequences, Gingeras, T. R., Milao, J. P., Sciaky, P. and Roberts, R. J., Nucleic Acid Res., Vol. 7, 1979, pp. 529-545.
[H92] A Contig Assembly Program Based on Sensitive Detection of Fragments Overlap, Huang, X., Genomics, Vol. 14, 1992, pp. 18-25.
[HGST86] Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs, Harold, G., Galil, Z., Spencer, T. and Tarjan, R.,Combinatorial, Vol. 6, 1986, pp. 109-122.
[KM89] A Procedural Interface for a Fragment Assembly Tool, Kececioglu, D. J. and Myers, W. E., Technical Reports; Department of Computer Science; The University of Arizona, Vol. 89, No. 5, 1989.
[KM95] Combinational Algorithms for DNA Sequence Assembly, Kececioglu, D. J. and Myers, W. E., Algorithmica, Vol. 13, 1995, pp. 7-51.
[KLT2001] A Probabilistic Approach to Sequence Assembly Validation, Kim, S., Liao, L. and Tomb, J. F., Workshop on Data Mining in Bioinformatics, 2001.
[M93] Rethinking the DNA Fragment Assembly Problem, Meidanis, J., 1993.
[M95] Towards Simplifying and Accurately Formulating Fragment Assembly, Myers, E. W.,J. Comput. Biology, Vol. 2, 1995, pp. 275-290.
[PTW2001] A New Approach to Fragment Assembly in DNA Sequencing, Pevzner, P. A., Tang, H. and Waterman, M. S., RECOMB Montreal; Canada, 2001, pp. 256-267.
On Sequence Alignment
[AAS2000] On Approximation Algorithms for Local Multiple Alignment, Akutsu, T.,Arimura, H.and Shimozono, S., RECOMB TOKYO, 2000, pp. 1-7.
[AKMSW87] Geometric Applications of a Matrix-Searching Algorithm, Aggarwal, A., Klawe, M., Moran. S., Shor, P. and Wilber, R., Algorithmica, Vol. 2, 1987, pp. 195-208.
[AL89] Trees Stars and Multiple Biological Sequence Alignment, Altschul, S. F. and Lipman, D. J., SIAM J. Appl. Math.,Vol. 49, 1989, pp.197-209.
[B95] A Space Efficient Algorithm for Finding the Best Nonoverlapping Alignment Score, Benson, G., Theoret. Comput. Sci., Vol. 145, 1995, pp. 357-369.
[BLP94] Approximation Algorithms for Multiple Sequence Alignment, Bafna, V., Lawler, E. L. and Pevzner, P., Proc. of the 5th Annual Symp. on Combin. Pattern Matching(CPM'94). Lecture Notes in Computer Science, Vol.807, 1974, pp. 43-53.
[BLP97] Approximation Algorithms for Multiple Sequence Alignment, Bafna, V., Lawler, E. and Pevzner, P., Theoretical Computer Science, Vol. 182, 1997, pp. 233-244.
[BM98] Discovering Internet Marketing Intelligencethrough Online Analytical Web Usage Mining, Buechner, A. and Mulvenna, M., SIGMOD Record, Vol. 27, 1998, pp. 54-61.
[BV2001] The Complexity of Multiple Sequence Alignment with SP-Score that is a Metric, Bonizzoni, P. and Vedova, G. D.,Theoretical Computer Science, Vol. 259, 2001, pp. 63-79.
[CHM92] Recent Developments in Linear-Space Alignment Methods: A Survey, Chao, K. M, Hardison, R. C. and Miller, W., J. Comput. Biol., Vol. 1, 1992, pp. 271-291.
[CL88] The Multiple Sequence Alignment Problem in Biology, Carrillo, H.and Lipman, D., SIAM J. Appl. Math, Vol. 48, 1988, pp. 1073-1082.
[CL92] Theoretical and Empirical Comparisons of Approximate String Matching Algorithms, Chang, W. I. and Lampe, J., In Proceedings of the 3rd Symposium on Combinatorial Pattern Matching; Lecture Notes in Computer Science, Vol. 644, 1992, pp. 172-181.
[CPM92] Aligning Two Sequences within a Specified Diagonal Band, Chao, K. M., Pearson, W. R. and Miller, W., Comput. Appl. BioSciences, Vol. 8, 1992, pp. 481-487.
[CWC92] A Survey of Multiple Sequence Comparison Methods, Chan, S. C., Wong, A. K. C. and Chiu, D. K.Y.,Bull. Math. Biol.,Vol. 54, 1992, pp. 563-598.
[DH75] Sequence Comparison by Dynamic Programming, Delcoigne, A. and Hansen, P., Biometrika, Vol. 62, 1975, pp. 661-664.
[FD87] Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees, Feng, D. and Doolittle, R., J. Molec. Evol.,Vol. 25, 1987, pp. 351-360.
[FFB2000] A Task-Based Architecture for Application-Aware Adjuncts, Farrell, R., Fairweather, P. and Breimer, E., Proceedings of the 2000 International Conference on Intelligent User Interfaces, 2000, pp. 82-85.
[G91] Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds, Gusfield, D., Tech. Report; Computer Science Division; University of California; Davis; CSE-91-4, 1991.
[G93] Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds, Gusfield, D., Bull. Mathematics Biology,Vol. 55, 1993, pp. 141-154.
[GCS2000] Evaluation Measures of Multiple Sequence Alignments, Gonnet, G. H., Korostensky, C. and Benner,S., Journal of Computational Biology, Vol. 7, No. 1-2, 2000, pp. 261-276.
[GBN94] Parametric Optimization of Sequence Alignment, Gusfield, D., Balasubramanian, K. and Naor, D., Algorithmica, Vol. 12, No. 4-5, 1994, pp.312-326.
[GG89] Speeding up Dynamic Programming with Applications to Molecular Biology, Galil, Z. and Giancarlo, R., Theoret. Comput. Sci., Vol. 64, 1989, pp. 107-118.
[GMP96] Gene Recognition via Spliced Sequence Alignment, Gelfand, M., Mironov, A. and Pevzner, P., Proc. Natl. Acad. Sci. USA, Vol. 93, 1996, pp. 9061-9066.
[J99] Reducing Gap-0 Multiple Alignment to Multiple Alignment, Just, W., Manuscript, 1999.
[KACGM93] The Maximun Weight Trace Alignment Problem in Multiple Sequence Alignment, Kececioglu, J., Apostolico, A., Crochemore, M., Galil, Z. and Manber, U.(Eds.), Combinatorial Pattern Maching 93; Padova Italy, 1993, Vol. 684, pp. 106-119.
[KM96] An Algorithm for Locating Non-Overlapping Regions of Maximum Alignment Score, Kannan, S. and Myers, E., SIAM J. Comput., Vol. 25, No. 3, 1996, pp. 648-662.
[LPSH2001] Visualization and Analysis of Clickstream Data of Online Stores for Understanding Web Merchandising, Lee, J., Podlaseck, M., Schonberg, E. and Hoch, R. J.,Data Mining Knowledge Discovery, Vol. 5, No. 1-2, 2001, pp. 59-84.
[LR99] Local Multiple Sequence Alignment Using Dead-End Elimination, Lukashin, A. V. and Rosa, J. J., Biogen Inc; Cambridge Center; USA, Vol. 15, No. 11, 1999, pp. 947-953.
[KRGS2001] Gene Structure Prediction and Alternative Splicing Analysis Using Genomically Aligned ESTs,Kan, Z., Rouchka, E. C., Gish, W. R.andStates, D. J., Genome Research, Vol. 11, 2001, pp. 889 –900.
[L88] Computational Molecular Biology Sources and Methods for Sequence Analysis,Lesk, A. ed., Oxford University Press, 1988.
[LAK89] A Tool for Multiple Sequence Alignment,Lipman, D. J., Altschul, S. F. and Kececioglu, J. D.,Proc. Nat.Acad Sci.,Vol. 86, 1989,pp. 4412-4415.
[LMW99] Finding Similar Regions in Many Sequences, Li, M., Ma, B. and Wang, L., Proc. 31st ACM Symp. Theory of Computing (STOC 99), 1999.
[LP2000] RNA Pseudoknot Prediction in Energy Based Models, LyngsØ, R. B. and Pedersen, C. N. S., Journal of Computational Biology, Vol.7,2000, pp. 409-427.
[LU2001] On the Common Substring Alignment Problem, Landau, G. and Ukelson, M., Journal of Algorithms, Vol. 41, 2001, pp. 338-359.
[M88] A Flexible Multiple Sequence Alignment Program, Martinez, M, Nucleic Acids Res., Vol. 16, 1988, pp. 1683-1691.
[MFDW97] DIALIGN: Finding Local Similarities by Multiple Sequence Alignment, Morgenstern, B., Frech, K., Dress, A. and Werner, T., GSF-National Research Center for Environment and Health, 1997.
[MRPG98] Performance-Guarantee Gene Predictions via Spliced Alignment, Mironov, A., Roytberg, M., Pevzner, P. and Gelfand, M., Genomics 51 A.N. GE985251, 1998, pp. 332-339.
[MW97] NearOptimalMultipleAlignment within a Band in Polynomial Time,Ma, B. and Wang, L.,in the Proc. 32ndACM, pp. 1-23.
[NW70] A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins, Neddleman, S. B. and Wunsch, C. D., J. Mol. Biol., Vol. 48, 1970, pp. 443-453.
[P92] Multiple Alignment; Communication Cost and Graph Matching, Pevzner, P. A., SIAM Journal on Applied Mathematics, Vol. 52, No. 6, 1992, pp. 1763-1779.
[S80] The Theory and Computations of Evolutionary Distances: Pattern Recognition, Sellers, P. H., J. Algorithms, Vol. 1, 1980, pp. 359-154.
[S2001] Non-Approximability of Weighted Multiple Sequence Alignment, Siebert, B., COCOON, 2001, pp. 75-85.
[SBDGGHHLMMPS91] A System for Distributed Intrusion Detection, Snapp, S., Brentano, J., Dias, G., Goan, T., Grance, T., Heberlein, L., Ho, C., Levitt, K., Mukerjee, B., Mansur, D., Pon, K. and Smaha, S., COMPCON Spring 91; the 36th IEEE International Computer Conference, 1991, pp. 170-176.
[SM86] A Multiple Sequence Alignment Program, Sobel, E. and Martinez, M., Nucleic Acids Res., Vol. 14, 1986, pp. 363-374.
[SP97] Las Vegas algorithms for Gene Recognition: Suboptimal and Error-Tolerant Spliced Alignment, Sze, S. and Pevzner, P. J. Comp. Biol., Vol. 4, No. 3, 1997, pp. 297-309.
[SYYH2002] Super Pairwise Alignment (SPA): An Efficient Approach to Global Alignment for Homologous Sequence, Shen, S. Y., Yang, J., Yao, A. and Hwang, P. I., Journal of Computational Biology, Vol. 9, 2002, pp. 477-486.
[SZ90] Fast Algorithm for the Unit Cost Editing Distance between Trees, Shasha, D. and Zhang, K., J. Algorithms, Vol. 11, 1990, pp. 581-621.
[T90] Hierarchical Method to Align Large Numbers of Biological Sequences, Taylor, W. R.,Methods Enzymology,Vol. 183, 1990, pp. 456-474.
[UHLU] Using Repeats to Speedup DNA Sequence Alignment, Ukelson, M., Horesh, Y., Landau, G. and Unger, R., Private Communication.
[WJ94] On the Complexity of Multiple Sequence Alignment, Wang, L. and Jiang, T., Journal of Computation Biology, Vol. 1, 1994, pp. 337-348.
[W95] A Simplified Proof of the NP- and MAX SNP-Hardness of Multiple Sequence Tree Alignments, Wareham, H. T., J. Comput. Biol., Vol. 2, No. 4., 1995, pp. 509-514.
[WJ94] On the Complexity of Multiple Sequence Alignment, Wang, L. and Jiang, T., J. Comput. Biol., Vol. 1, 1994, pp. 337-348.
[WSB76] Some Biological Sequence Metrics, Waterman, M. S., Smith, T. F. and Beyer, W. A., Adv. In Math., Vol. 20, 1976,pp. 367-378.
[Z96] A Constrained Edit Distance between Unordered Labeled Trees, Zhang, K., Algorithmica, Vol. 15, 1996, pp. 205-222.
[ZSS92] On the Editing Distance between Unordered Labeled Trees, Zhang, K., Statman, R. and Shasha, D., Information Processing Letters, Vol. 42, 1992, pp. 133-139.
On Evolutionary Trees
[AG83] Human Mitochondrial DNA Variation and Evolution: Analysis of Nucleotide Sequences from Seven Individuals, Aquadro, C. F. and Greenberg, B. D., Genetics, Vol. 103, 1983, pp. 287-312.
[AK97] Maximun Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms, Amir, A. and Keselman, D., SIAM J. Comput., Vol. 26, 1997, pp. 1656-1669.
[B71] The Recovery of Trees from Measures of Dissimilarity, Buneman, P., Mathematics in the Archaeological and Historical Sciences, 1971, pp. 387-395.
[BBJKLWZ2000] Practical Algorithm for Recovering the Best Supported Edges in an Evolutionary Tree, Berry, V., Bryant, D., Jiang, T., Kearney, P., Li, M., Wareham, T. and Zhang, H., Proc. 11th Annual ACM-SIAM Symp. on Discrete Algorithms, 2000.
[BPWW82] Mitochondrial DNA Sequences of Primates: Tempo and Mode of Evolution,Brown, W. M., Prager, E. M., Wang, A. and Wilson, A. C.,Journal of Molecular Evolution, Vol.18, 1982, pp.225-239.
[BSLGDV98] The Discovery of Two New Divergent STLVs Has Implications for the Evolution and Epidemiology of HTLVs, Brussel, M. V., Salemi, M., Liu, H. F., Goubau, P., Desmyter, J. and Vandamme, A. M., Rev. Med. Virol., Vol. 9, 1999, pp. 155-170.
[CBW84] Polymorphic Sites and the Mechanism of Evolution in Human Mitochondrial DNA, Cann, R. L., Brown, W. M. and Wilson, A. C., Genetics, Vol. 106, 1984, pp. 479-499.
[CR89] A Fast Algorithm for Constructing Trees from Distance Matrices, Culbertson, J. C. and Rudnicki, P., Inform. Process. Lett., Vol. 30, No. 4., 1989, pp. 215-220.
[CSW87] Mitochondrial DNA and Human Evolution, Cann, R. L., Stoneking, M. and Wilson, A. C., Nature, Vol. 325, 1987, pp. 31-36.
[F81] Evolutionary Trees from DNA Sequences: A Maximum Likelihood Approach, Felsenstein, J., J. Molecular Evolution, Vol. 17, 1981.
[F88] Phylogenies from Molecular Sequences: Inference and Reliability, Felsenstein, J., Annu. Rev. Genet, Vol. 22, 1988, pp. 521-565.
[FKW95] A Robust Model for Finding Optimal Evolutionary Trees, Farach, M., Kannan, S. and Warnow, T., Algorithmica, Vol. 13, No. 1-2, 1995, pp. 155-179.
[FM67] Construction of Phylogenetic Trees, Fitch, W. M. and Margoliash, E., Science, Vol. 155, No. 20, 1967, pp. 279-284.
[FT97] Sparse Dynamic Programming for Evolutionary Tree Comparison, Farach, M. and Thorup, M., SIAM J. Comput., Vol. 26, 1997, pp. 210-230.
[HH90] Intraspecific Nucleotide Sequence Differences in the Major Noncoding Region of Human Mitochondrial DNA, Horai, S. and Hayasaka, K.,Am. J. Hum Genet., Vol. 46, No. 828, 1990.
[HH91] Time of the Deepest Root for Polymorphism in Human Mitochondrial DNA, Hasegawa, M. and Horai, S., Journal of Molecular Evolution, Vol. 32, 1991, pp. 37-42.
[HT84] Fast Algorithms for Finding Nearest Common Ancestors, Harel, D. and Tarjan, R. E., SIAM J. Comp, Vol. 13, No. 2, 1984, pp. 338-355.
[JKL2001] A Polynomial Time Approximation Scheme For Inferring Evolutionary Trees From Quartet Topologies and Its Application, Jiang, T., Kearney, P. and Li, M., SIAM Journal Comput., Vol. 30, No. 6, 2001, pp. 1942-1961.
[JLW94] Aligning Sequences via an Evolutionary Tree, Jiang, T., Lawler, E. L. and Wang, L., Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 1994, pp. 760-769.
[KG98] Reconstructing a History of Recombination from a Set of Sequences, Kececioglu, J. and Gusfield, D., Discrete Applied Mathematics, Vol. 88, 1998, pp. 239-260.
[KHM97] Inferring Evolutionary Trees from Ordinal Data, Kearney, P., Hayward, R. B. and Meijer, H. Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 418-426.
[KLW96] Determining the Evolutionary Tree Using Experiments, Kannan, S. K., Lawler, E. L. and Warnow, T. J., J. Algorithms, Vol. 21, 1996, pp. 26-50.
[KW94] Inferring Evolutionary History from DNA Sequences, Kannan, S. K. and Warnow, T. J., SIAM Journal on Computing, Vol. 23, No. 4, 1994, pp. 713-737.
[KW95] Tree Reconstruction from Partial Orders, Kannan, S. and Warnow, T., SIAM J. Computing, Vol. 24, 1995, pp. 511-519.
[KWY98] Computing the Local Consensus of Trees, Kannan, S., Warnow, T. and Yooseph, S., SIAM Journal on Computing, Vol. 27, No. 6, 1998, pp.1695-1724.
[LBC96] An Evolutionary Trace Method Defines Binding Surfaces Common to Protein Families, Lichtarge, O., Bourne, H. R. and Cohen, F. E., Journal Comput. Biol., Vol. 257, 1996, pp. 342-358.
[LCJDLG98] Molecular Analysis of GB Virus C Isolates in Belgian Hemodialysis Patients, Liu, H. F., Cornu, C., Jadoul, M., Dahan, K., Loute, G. and Goubau, P., Journal of Medical Virology, Vol. 55, 1998, pp. 118-122.
[LMTDDG2000] High Prevalence of GB Virus C/Hepatities G Virus in Kinshasa; Democratic Republic of Congo: A Phylogenetic Analysis, Liu, H. F., Muyembe, J. J., Tamfum, J. J., Dahan, K., Desmyter, J. and Goubau, P., Journal of Medical Virology, Vol. 60, 2000, pp. 159-165.
[S75] Minimum Mutation Tree of Sequences, Sankoff, D.,SIAM J. Appl. Math.,Vol. 28, 1975, pp. 35-42.
[S89] Origin of Early Modern Humans, Stringer,C. B., ibid, 1989, pp. 232-244.
[S92] The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees, Steel, M., Journal of Classification, Vol. 9, 1992, pp. 91-116.
[SA83] Phylogeny and Classification of Birds Based on the Data of DNA-DNA-Hybridization, Sibley, C. G. and Ahlquist, J. E., Curr. Ornithol., Vol. 1, 1983, pp. 245-292.
[SA88] Genetic and Fossil Evidence for the Origin of Modern Humans, Stringer, C. B. and Andrews, P., Science, Vol. 239, 1988, pp. 1263-1268.
[SH96] Quartet Puzzling : A Quartet Maximum-Likelihood Method for Reconstructing Tree Topologies, Strimmer, K. and Haeseler, A. V., Molecular Biology and Evolution, Vol. 13, 1996, pp. 964-969.
[SJBW90] Geographic Variation in Human Mitochondrial DNA from Papua New Guinea, Stoneking, M., Jorde, L. B., Bhatia, K. and Wilson, A. C., Genetics, Vol. 124, 1990, pp.717-733.
[SN87] The Neighbor-Joining Method : A New Method for Reconstructing Phylogenetic Trees, Staitou, N. and Nei, M., Molecular Biology and Evolution, Vol. 4, 1987, pp. 406-425.
[SV88] On Finding Lowest Common Ancestors: Simplification and Parallelization, Schieber, B. and Vishkin, U., SIAM J. Comput., Vol. 17, 1988, pp. 1253-1262.
[T91] Human Origins and Analysis of Mitochondrial DNA Sequences, Templeton, A., Science, Vol. 255, 1991, pp. 737.
[VPHKW89] Mitochondrial DNA Sequences in Single Hairs from a Southern African Population, Vigilant, R., Pennington, R., Harpending, H., Kocher, T. D. and Wilson, A. C., Proc. Natl. Acad. U.S.A., Vol. 86, 1989, pp. 9350-9354.
[VSHHW91] African Populations and the Evolution of Human Mitochondrial DNA, Vigilant, L., Stoneking, M., Harpending, H., Hawkes, K. and Wilson, A. C., Science, Vol. 253, No. 27, 1991, pp. 1503-1507.
[WJ94] On the Complexity of Multiple Sequence Alignment, Wang, L. and Jiang, T., Journal of Computational Biology, Vol. 1, No. 4, 1994, pp. 337-348.
[WLBCRT2000] A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees, Wu, B. Y., Lancia, G., Bafna, V., Chao, K. M., Ravi, R. and Tang, C. Y., SIAM J. on Computing, Vol. 29, No. 3, 2000, pp. 761-778.
[WSSB77] Additive Evolutionary Trees, Waterman, M. S., Smith, T. F., Singh, M. and Beyer, W. A., Journal Theoretical Biology, Vol. 64, 1977, pp. 199-213.
[WZJS94] A System for Approximate Tree Matching, Wang, J. T. L., Zhang, K., Jeong, K. and Shasha, D., IEEE Transactions on Knowledge and Data Engineering, Vol. 6, No. 4, 1994, pp. 559-571 1041-4347.
[VSHHW91] African Populations and the Evolution of Human Mitochondrial DNA,Vigilant L., Stoneking M., Harpending H., Hawkers K. and Wilson A. C., Science, New Series, Vol. 253, No. 5027, 1991, pp.1503-1507.
On Superstrings
[AS95] Improved Length Bounds for the Shortest Superstring Problem, Armen, C. and Stein, C., in Proceedings 5th International Workshop on Algorithms and Data Structures; Lecture Notes in Comput. Sci., Vol. 955, 1995, pp. 494-505.
[AS98] 2 2/3 Superstring Approximation Algorithm, Armen, C. and Stein, C., Discrete Applied Mathematics, Vol. 88, No. 1-3, 1998, pp. 29-57.
[AS96] A 2 2/3 Approximation Algorithm for the Shortest Superstring Problem, Armen, C. and Stein C., in Proceedings Combinational Pattern Matching, Lecture Notes in Comput. Sci., Vol. 1075, 1996, pp. 87-101.
[BJJ97] Rotations of Periodic Strings and Short Superstrings, Breslauer, D., Jiang, T. and Jiang, Z., J. Algorithms, Vol. 24, No. 2, 1997, pp. 340-353.
[BJLTY91] Linear Approximation of Shrotest Superstrings, Blum, A., Jiang, T., Li, M., Tromp, J. and Yannakakis, M., in Proceedings 23th Annual ACM Symposium on Theory of Computing; ACM, 1991, pp. 328-336.
[E90] A linear time algorithm for finding approximate shortest common superstrings, Esko, U., Algorithmica, Vol. 5, 1990, pp. 313-323.
[FS98] Greedy Algorithms for the Shortest Common Superstring that are Asymptotically Optimal, Frieze, A. and Szpankowski, W., Algorithmica, Vol. 21, No. 1, 1998, pp. 921-36.
[GMS80] On Finding Minimal Length Superstring, Gallant,J., Maier,D. and Storer, J.,Journal of Computer and System Sciences, Vol. 20, 1980, pp. 50-58.
[J89] Approximation Algorithms for the Shortest Common Superstring Problem, Jonathan, T., Information and Computation, Vol. 83, 1989, pp. 1-20.
[JL95] On the Approximation of Shortest Common Supersequences and Longest Common Subsequences, Jiang, T. and Li, M.,SIAM Journal on Computing, Vol. 24, No. 5, 1995, pp. 1122-1139.
[JU88] A Greedy Approximation Algorithm for Constructing Shortest Common Superstrings, Jorma, T. and Ukkonen, E., Theoretical Computer Science, Vol. 57, 1988, pp. 131-145.
[KPS94] Long Tours and Short Superstrings, Kosaraju, S. R., Park, J. K. and Stein, C., Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166-177.
[S99] A 2 1/2 Approximation Algorithm for Shortest Superstring, Sweedyk, Z., SIAM J. on Computing, Vol. 29, No. 3, 1999, pp. 954-986.
[TY93] Approximating Shortest Superstrings, Teng, S. and Yao, F., Proc. 34th Annual IEEE Symposium on Foundations of Computer Science; IEEE Computer Society Press; Los Alamitos; CA, 1993, pp. 158-165.
On Protein Structure
[A96] Protein Structure Alignment Using Dynamic Programming and Iterative Improvement, Akutsu, T., IEICE Trans. Inf. & Syst., Vol. E78-D, No. 0, 1996, pp. 1-8.
[AGMML90] Basic Local Alignment Search Tool, Altschul, S. F., Gish, W., Miller, W., Myers, E. W. and Lipman, D., J. Mol. Biol., Vol. 215, 1990, pp. 403-410.
[AH94] On the Approximation of Largest Common Subtrees and Largest Common Point Sets,Akutsu, T. and Halldorsson, M. M., Lecture Notes in Computer Science, 1994, pp. 405-413.
[AM97] On the Approximation of Protein Threading, Akutsu, T. and Miyano, S., RECOMB, 1997, pp. 3-8.
[AS99] Protein Threading Based on Multiple Protein Structure Alignment, Akutsu, T. and Sim, K. L., Genome Informatics, Vol. 10, 1999, pp. 23-29.
[AT98] Linear Programming Based Approach to the Derivation of a Contact Potential for Protein Threading, Akutsu, T. and Tashimo, H., Proc. Pacific Symposium on Biocomputing 1998, 1998, pp. 413-424.
[AMSZZML97] Gapped BLAST and PSI BLAST: A New Generation of Protein Database Search, Altschul, S. F., Madden, T. L., Schaffer, A. A., Zhang, J., Zhang, Z., Miller, W. and Lipman, D. J., Nucleic Acids Research, Vol. 25, No. 17, 1997, pp. 3389-3402.
[B76] The Protein Data Bank: A Computer-Based Archival File for Macromolecular Structure, Bernstein, F. C. et. al., J. Molecular Biology, 1976, pp. 535-542.
[BKWMBRKST76] The Protein Data Bank: A Computer-Based Archival File for Macromolecular Structures, Bernstein, F. C., Koetzle, T. F., Williams, G. J. B., Meyer jr., E. F., Brice, M. D., Rodgers, J. R., Kennard, O., Shimanouchi, T. and Tasumi, M., J. Molecular Biology, Vol. 112, 1976, pp. 535-542.
[BL98] Protein Folding in the Hydrophobic-Hydrophilic(HP) Model is NP-Complete, Berger, B. and Leighton, T., Journal of Computational Biology, Vol. 5, No. 1, 1998, pp. 27-40.
[BLE91] A Method to Identify Protein Sequences that Fold into a Known Three-Dimensional Structures, Bowie, J. U., Luthy, R. and Eisenberg, D., Science, 1991, pp. 164-170.
[BT91] Introduction to Protein Structure, Branden, C. and Tooze, J., Garland Publishing; New Yourk, 1991.
[BYZRS2000] Comprehensive Statistical Method for Protein Fold Recognition, Bienkowska, J. R., Yu, L., Zarakhovich, S., Rogers Jr, R. G. and Smith, T. F., RECOMB 2000 Tokyo Japan, 2000, pp. 76-85.
[CGPPY98] On the Complexity of Protein Folding, Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A. and Yannakakis, M., Journal of Computational Biology, Vol. 5, No. 3, 1998, pp. 423-465.
[CPMLC91] Pattern Recognition and Protein Structure Prediction, Cohen, B. I., Presenell, S. R., Morris, M., Langridge, R. and Cohen, F. E., System Sciences,Vol.1, 1991, pp. 574-584.
[CPM92] Aligning Two Sequences within a Specified Diagonal Band, Chao, K. M., Pearson, W. R. and Miller, W., CABIOS, No. 8, 1992, pp. 481-487.
[D69] Computer Analysis of Protein Evolution, Dayhoff, M. O., Sci. Amer., 1969, pp. 86-96.
[D2002] A Genomic Regulatory Network for Development, Davidson, E. H., Science, Vol. 295, 2002, pp. 1669-1678.
[DPR97] Protein Structure Prediction and Potential Energy Landscape Analysis Using Continuous Global Minimization, Dill, K. A., Phillips, A. T. and Rosen, J. B., RECOMB, 1997, pp. 109-117.
[EGGI92] Sparse Dynamic Programming I: Linear Cost Functions, Eppstein, D., Galil, Z., Giancarlo, R. and Italiano, G. F., Journal of the Association for Computing Machinery, Vol. 39, No. 3, 1992, pp. 519-545.
[EGGI92] Sparse Dynamic Programming II: Convex and Concave Cost Functions, Eppstein, D., Galil, Z., Giancarlo, R. and Italiano, G., J. Assoc. Comput. Mach., Vol. 39, 1992, pp. 546-567.
[G93] Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds, Gusfield, D., Bulletin of Mathematical Biology, Vol. 55, 1993, pp. 141-154.
[GBDK89] An NTP-Binding Motif is the Most Conserved Sequence in a Highly Diverged Monophyletic Group of Proteins Involved in Positive Strand RNA Viral Replication, Gorbalenya, A. E., Blinov, V. M., Donchenko, A. P. and Koonin, E. V., J. Molec. Evol.,Vol. 28, 1989, pp. 256-268.