High Performance Algorithms

 

Selected Publications

 

Journal Publications

 

  1. Alon N, Asodi V, Cantor C, Kasif S, Rachlin J. Multi-node graphs: a framework for multiplexed biological assays. J Comput Biol. 2006 Dec;13(10):1659-72. PMID: 17238837
  2. Formula dissection: A parallel algorithm for constraint satisfaction. Reif, J. H., Kasif, S., and Sherlekar, D.  Comput. Math. Appl. 55, 6 (Mar. 2008), 1170- 1177 (republished from a 1987 conference version).
  3. Noga Alon, Richard Beigel and Simon Kasif and Steven Rudich and Benny Sudakov, “Learning a Hidden Matching“, SIAM Journal of Computing, 2004.
  4. Wu CJ, Fu Y, Murali TM, Kasif S.  Gene expression module discovery using Gibbs sampling. Genome Inform. 2004;15(1):239-48. PMID: 15712126
  5. Letovsky S, Kasif S.  Predicting protein function from protein/protein interaction data: a probabilistic approach.  Bioinformatics. 2003;19 Suppl 1:i197-204. PMID: 12855458
  6. Kasif S, Weng Z, Derti A, Beigel R, DeLisi C. A computational framework for optimal masking in the synthesis of oligonucleotide microarrays. Nucleic Acids Res. 2002 Oct 15;30(20):e106. PMID: 12384608
  7. Tettelin H, Radune D, Kasif S, Khouri H, Salzberg SL.  Optimized multiplex PCR: efficiently closing a whole-genome shotgun sequencing project. Genomics. 1999 Dec 15;62(3):500-7. PMID: 10644449
  8. Delcher AL, Harmon D, Kasif S, White O, Salzberg SL. Improved microbial gene identification with GLIMMER. Nucleic Acids Res. 1999 Dec 1;27(23):4636-41. PMID: 10556321
  9. Delcher AL, Kasif S, Fleischmann RD, Peterson J, White O, Salzberg SL. Alignment of whole genomes. Nucleic Acids Res. 1999 Jun 1;27(11):2369-76. PMID: 10325427
  10. Kasif, S.,  “Datascope: Mining Biological Sequences”, special issue on Data Mining, IEEE Intelligent Systems,  pp. 38–45, 1999.
  11. Kasif, S., Salzberg, S., Waltz, D., J. Rachlin, and Aha, D., “Towards of a Framework for Memory-Based Reasoning”, Artificial Intelligence, pp. 287–311, 1998.
  12. Kasif, S., “Towards a Constraint-Based Engineering Framework for Algorithm Design and Application”, Journal of Constraints, 1997.
  13. Delcher, A, A. Grove, S. Kasif and J. Pearl, “Logarithmic Time Queries and Updates in Probabilistic Networks”, Journal of Artificial Intelligence Research, Vol. 4., pp. 37–59, 1996.
  14. Waltz, D. and S. Kasif, “On Reasoning from Data”, Computing Surveys, 1996.
  15. Delcher, A. and S. Kasif, “Term Matching on a Mesh-Connected Array of Processors”, Annals of Mathematics and Artificial Intelligence, Volume 14, pp.177–186, 1995.
  16. Murthy, S., S. Kasif and S. Salzberg, “ System for Induction of Oblique Decision Trees”, Journal of Artificial Intelligence Research, 2:1, pp.1–33, 1994.
  17. Heath, D., S. Kasif, S. R. Kosaraju, S. Salzberg and G. Sullivan, “Learning Nested Concept Classes with Limited Memory”, Journal of Experimental and Theoretical AI, 1996.
  18. Kasif, S., “Optimal Parallel Algorithms for Quad-Tree Problems”, Journal of Computer Vision and Image Processing, pp.281–285, May 1994.
  19. Kasif, S. and A. Delcher, “Analysis of Local Consistency in Parallel Constraint Networks”, Artificial Intelligence, 69, pp.307–327, 1994.
  20. Heath, D. and S. Kasif, “On Voronoi Covers with Applications to Machine Learning”, Computational Geometry: Theory and Applications, pp. 289-305, Nov. 1993.
  21. Kasif, S., S. Banerjee, A. Delcher and G. Sullivan, “Some Results on the Complexity of Symmetric Connectionist Networks”, Annals of Mathematics and Artificial Intelligence, pp.327-344, Nov. 1993.
  22. Delcher, A. and S. Kasif,  “Efficient Parallel Term Matching and Anti-Unification”, Journal of Automated Reasoning, pp.  391–406, 1992.
  23. Kasif, S., “On the Parallel Complexity of Discrete Relaxation in Constraint Networks”, Artificial Intelligence, pp. 275-286, October 1990.
  24. Delcher, A. and S. Kasif, “Some Results On the Complexity of Maintaining Data Flow Dependencies in Parallel Logic Programs”, Journal of Logic Programming, pp.229–241, April 1989.
  25. Kasif, S., “Control and Data Driven Execution of Logic Programs: A Comparison”, Journal of Parallel Programming.Vol.15, No.1, pp.73–100, February 1987.
  26. Kasif, S., L. Kitchen and A. Rosenfeld, “A Hough Transform Technique for Subgraph Isomorphism”, Pattern Recognition Letters. Vol.2, pp.83–88, December 1983.
  27. Kasif, S. and A. Rosenfeld, “Pyramid Linking as a Special Case of Isodata”, IEEE Transactions on Systems, Man and Cybernetics, Vol.SMC-13, No.1, January 1983.

 

Books, Books Chapters and Special Reports

 

  1.  S. Kasif and A. Delcher, “Analysis of Local Consistency in Parallel Constraint Networks”, Principle and Practice of Constraint Programming, published by MIT press, editors Pascal van Henteryck and V.J. Saraswat, 1994.
  2. Heath, D., S. Kasif and S. Salzberg, “Committees of Decision Trees”, Cognitive Technology, North Holland Publishers, 1995
  3. Simon Kasif and Stuart Russell (Eds.), Proceedings of the AAAI Fall Symposium on Learning Complex Behaviors, AAAI Press, 1996.
  4. J. Flannagan, T. Huang, P. Jones, and S. Kasif, “Human Centered Systems: Information, Interactivity and Intelligence”, Executive NSF Steering Committee Report, July, 1997.
  5. R. Grossman, S. Kasif, J. Ullman, et al,  “Data Mining”, Executive Committee NSF Report, 1998.
  6. Kasif, S. and A. Delcher, “Biological Data Modeling using Probabilistic Networks”, in Salzberg, S., D. Searls, and S. Kasif, “Computational Methods in Molecular Biology”, Elsevier, Publ. 1998.
  7. S. Salzberg, D. Searls and S. Kasif, eds, “Computational Methods in Molecular Biology”, Elsevier Publ. 1998. (2nd Printing, February 1999).
  8. Rich Roberts, Peter Karp, Simon Kasif and Stuart Linn, “An Experimental Approach to Gene Function”, Executive Report, American Academy for Microbiology.
  9. Satoru Miyano Jill Mesirov, Simon Kasif, Sorin Istrail Pavel Pevzner, Michael Waterman, Research in Computational Molecular Biology: 9th Annual International Conference, RECOMB 2005, Cambridge, MA, USA, May 14-18, 2005, Proceedings Lecture Notes in Bioinformatics.

 

 

Papers in Peer-Reviewed Conferences

Publications in very selective conferences with acceptance rates of 25% or less are marked with asterisks *. These papers are typically considered equal to a journal publication in Computer Science.

 

  1. *Eisinger, N., S. Kasif and J. Minker, “Logic Programming: A Parallel Approach”, First International Logic Programming Conf., Faculte des Sciences de Luminy Marseille, France, pp.71–77, September 1982.
  2. Kasif, S., M. Kohli and J. Minker, “PRISM—A Parallel Inference System Based on Logic”, Logic Programming Workshop, pp.123–152, Portugal, June 1983.
  3. *Kasif, S., M. Kohli and J. Minker, “Control Facilities of PRISM—A Parallel Inference System Based on Logic”, International Joint Conf. on Artificial Intelligence, August 1983.
  4.  Chakravarthy, U. S., S. Kasif, M. Kohli, J. Minker and D. Cao, “Logic Programming on ZMOB: A Highly Parallel Machine”, Proc. 1982 International Conf. on Parallel Processing, IEEE Press, pp.347—349 New York, 1982.
  5. *Kasif, S. and A. Rosenfeld, “The Fixpoints of Images and Scenes”, Conf. on Computer Vision and Pattern Recognition, pp.454-456, June 1983.
  6. *Kasif, S. and J. Minker, “The Intelligent Channel:  A Scheme for Result Sharing in Parallel Logic Programs”, International Joint Conf. on Artificial Intelligence, pp.29-31, August 1985.
  7. *Kasif, S., “On the Parallel Complexity of Some Constraint Satisfaction Problems”, National Conf. on Artificial Intelligence (AAAI-86), pp.349-353, August 1986.
  8. Kasif, S., J. Reif and D. Sherlekar, “Formula Dissection: A Parallel Algorithm for Constraint Satisfaction”, IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pp.51-57, October 1987.
  9. Delcher, A. and S. Kasif, “On the Complexity of Incremental Parallel Computations in Artificial Intelligence”, IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pp.59-64, October 1987.
  10. Kasif, S., “Efficient Parallel Quad-Tree Algorithms”, Proc. of 1988 ICAI, Tel Aviv, Israel, pp.353-363, December 1988.
  11. Delcher, A. and S. Kasif, “Parallel Term Matching on Mesh Connected Computers”, Proc. of 1988 ICAI, Tel Aviv, Israel, pp.~441-452, December 1988.
  12. *Kasif, S., “Parallel Solutions to Constraint Satisfaction Problems”, IEEE Conf. on Principles of Knowledge Representation and Reasoning, pp. 180-187, May 1989.
  13. *Delcher, A. and S. Kasif, “Parallel Term Matching and Anti-Unification”, International Conf. on Logic Programming, pp.355–369, June 1990.
  14. *Heath, D., S. Kasif, S. R. Kosaraju, S. Salzberg and G. Sullivan, “Learning Nested Concept Classes with Limited Storage”, Proceedings of the International Joint Conference on Artificial Intelligence(IJCAI-91), pp. 777-782, 1991.
  15. *Salzberg, S., D. Heath, A. Delcher and S. Kasif, “Learning with a Helpful Teacher”, Proceedings of the International Joint Conference on Artificial Intelligence, (IJCAI-91), pp. 705-711, 1991.
  16. *S. Kasif and A. Delcher, “Improved Decision Making in Game Trees: Recovering from Pathology”, Proceedings of the National Conference on Artificial Intelligence (AAAI-92), pp. 513-518, July 1992.
  17. D. Heath, S. Kasif and S. Salzberg, “Learning Oblique Decision Trees”, Computational Learning Theory and Natural Learning Systems, 1992.
  18. Kasif, S. and A. Delcher, “Analysis of Local Consistency in Parallel Constraint Networks”, International Conference on Artificial Intelligence and Vision, pp. 217-231, 1992.
  19. S. Kasif, “Iterative Focusing and Hashing: An Alternative to Alpha-Beta”, International Conference on Artificial Intelligence and Vision, pp. 59-72, 1992.
  20. *D. Heath, S. Kasif and S. Salzberg, “Learning Oblique Decision Trees”, Proceedings of the International Joint Conference on Artificial Intelligence, (IJCAI 93), pp. 1002–1007, August 1993.
  21. *Murthy, S., S. Kasif, S. Salzberg and R. Beigel, “OC1: A Randomized Algorithm for Building Oblique Decision Trees”, Proceedings of the National Conference on Artificial Intelligence, (AAAI-93), pp. 322–327, July 93.
  22. Heath, D., S. Kasif and S. Salzberg, “k-DT: A Multi-Tree Learning Method”, Proceedings of the Second International Workshop on Multi-strategy Learning (pp. 138–149), Harpers Ferry, West Virginia, 1993.
  23. *Delcher, A., S. Kasif, H. Goldberg and W. Xsu, “Protein Secondary-Structure Modeling with Probabilistic Networks”, International Conference on Intelligent Systems and Molecular Biology, pp. 109–117, 1993.
  24. *Delcher, A., S. Kasif, H. Goldberg and W. Xsu, “Application of Probabilistic Causal Trees to Analysis of Protein Secondary Structure”, Proceedings of the National Conference on Artificial Intelligence, pp. 316–321, July 1993.
  25. *Bright, J., Kasif, L. Stiller, “Exploiting Algebraic Structure in Parallel State-Space Search”, Proc. of the 11-th National Conf. on Artificial Intelligence, July 1994, (AAAI-94), pp. 1341-1346, preliminary version presented in the AAAI Symposium on Massively Parallel AI”, March 1993.
  26. *Rachlin, J., S. Kasif, S. Salzberg and D. Aha, “Toward of a better understanding of Memory-Based Classifiers”,  (plenary talk), Proceeding of the 11-th Intern. Conf. on Machine Learning, pp. 242–250, July 1994.
  27. *Fulton, T., S. Kasif and S. Salzberg, “Efficient Algorithms for Finding Multi-Way Splits for Decision Trees”, JHU TR, December 1993, Proceeding of the 12-th Intern. Conf. on Machine Learning, July 1995.
  28. *Delcher, A, A. Grove, S. Kasif and J. Pearl, “Logarithmic Time Queries and Updates in Probabilistic Networks”, Proceedings of the 1995 Conference on Uncertainty in AI, August 1995.
  29. D. Dobkin, D. Gunopoulous,  S. Kasif, “Induction of Low-Depth Decision Trees”, International Conference on Mathematics and Artificial Intelligence, 1996,
  30. S. Weiss, S. Kasif, and E. Brill, “Towards a Framework for Adaptive Information Retrieval”, AAAI Spring Symposium on Information Retrieval (1996).
  31. *T. Fulton, S., Kasif, S. Salzberg, and D. Waltz, “Local Induction of Decision Trees”, Proceedings of the 1996 Conference of Knowledge Discovery in Databases”, August 1996.
  32. R. Grossman, S. Bailey, S. Kasif, “Papyrous: A System for Distributed Data Mining”, Workshop on Distributed Data Mining, NYC, 1998.
  33. *Beigel, R., N. Alon, S. Apaydin, L. Fortnow, and S. Kasif, “An Optimal Multiplex PCR Protocol for Closing Gaps in Whole Genomes”, RECOMB, April 2001.
  34. * Noga Alon, Richard Beigel and Simon Kasif and Steven Rudich and Benny Sudakov, “Learning a Hidden Matching”, Foundations of Computer Science, FOCS 2002.
  35. T.M. Murali and S. Kasif, “Extracting Conserved Gene Expression Motifs from from Microarray Data”, Pacific Symposium on Biocomputing, January 2003.
  36. B. Logan, P. Moreno, B. Suzek, Z. Weng, and S. Kasif, “Remote Homology Detection Using Feature Vectors Formed Using Alignments of Small Motifs”, RECOMB 2002 (poster and patent 2000).
  37. D. Pervouchine, J. Graber, and S. Kasif, “Stable RNA Secondary Structure of Human Donor Splice Sites”, RECOMB 2002 (poster)
  38. M. Walker, V. Pavlovic, and S. Kasif, “A Comparative Genomic Method for Computational Identification of Prokaryotic Translation Initiation Sites”, RECOMB 2002 (poster)
  39. Y. Zheng, R. J. Roberts, and S. Kasif, “Computational Identification of Operons in Microbial Genomes”, RECOMB 2002 (poster).
  40. Murali TM, Kasif S.  Extracting conserved gene expression motifs from gene expression data. Pac Symp Biocomput. 2003;:77-88. PMID: 12603019
  41. *S. Letovsky and S. Kasif, “A Probabilistic Approach to Gene Function Assignment and Propagation in Protein Interaction Networks”, June 2003, ISMB 2003.

 

<BACK