Sorin Istrail's Publications
2009
Istrail, S., and Lam, F. Combinatorial Algorithms for Protein Folding in Lattice Models: A Survey of Mathematical Results. Communications in Information and Systems Journal (2009). [ pdf ]
Istrail, S., Pevzner, P., and Shamir, R. Special Issue Dedicated to Michael Waterman's 67th Birthday. Communications in Information and Systems, International Press (2009).
2007
Istrail, S., de Leon, S. B.-T., and Davidson, E. H. The Regulatory Genome and the Computer. Developmental Biology 310 (Oct. 2007), 187-195. [ pdf ]
2006
Samanta, M., Tongprasit, W., Istrail, S., Cameron, A., Tu, Q., Davidson, E., and Stolc, V. The transcriptome of the sea urchin embryo. Science 314 (Nov. 2006), 960-962. [ pdf ]
Sharan, R., Halldorsson, B. V., and Istrail, S. Islands of Tractability for Parsimony Haplotyping. IEEE Computer Society Press 3 (Sept. 2006), 303-311. [ pdf ]
Istrail, S. Randomness is Beautiful: in Search of von Neumann. Conduit 15, 1 (2006), 10-15. [ pdf ]
Sodergren, E., Weinstock, G., Davidson, E., ..., Istrail, S., and ... The Genome of the Sea Urchin Strongylocentrotus purpuratus. Science 314 (2006), 941-952. [ pdf ]
2005
Vega, F. M. D. L., Isaac, H., Collins, A., Scafe, C. R., Halldórsson, B. V., Su, X., Lippert, R. A., Kalush, F., O'Brian, S. J., Clark, A., Istrail, S., Hunkapiller, M. W., Spier, E. G., and Gilbert, D. The linkage disequilibrium maps of three human chromosomes across four populations reflect their demographic history and a common underlying recombination pattern. Genome Research 15 (2005), 454-462. [ pdf ]
Florea, L., DiFrancesco, V., Miller, J., Turner, R., Mobarry, C., Yao, A., Harris, M., Walenz, B., Dew, I., Merkulov, G., Charlab, R., Deng, Z., Istrail, S., Li, P., and Sutton, G. Gene and alternative splicing annotation with AIR. Genome Research 15, 1 (2005), 54-66. [ pdf ]
Halldorsson, B., Sharan, R., and Istrail, S. Islands of tractability for parsimony haplotyping. In Proceedings of the Stanford Conference on Computational Systems Biology (2005), pp. 65-72. [ pdf ]
Istrail, S., and Davidson, E. Logic functions of the genomic cis-regulatory code. In Proceedings of the National Academy of Sciences (2005), pp. 4954-4959. [ pdf ]
2004
Caprara, A., Carr, R., Istrail, S., Lancia, G., and Walenz, B. 1001 Optimal PDB structure alignments: integer programming methods for finding the maximum contact map overlap. Journal of Computational Biology 11, 1 (2004), 27-52. [ pdf ]
Halldorsson, B. V., Bafna, V., Lippert, R., Schwartz, R. S., Vega, F. M. D. L., Clark, A. G., and Istrail, S. Optimal haplotype block free selection of tagging SNPs for genome-wide association studies. Genome Research 14 (2004), 1633-1640. [ pdf ]
Istrail, S., Florea, L., Halldorsson, B. V., Kohlbacher, O., Schwartz, R. S., Yap, V. B., Yewdell, J., and Hoffman, S. Comparative immuno-peptidomics of humans and their pathogens. In Proceedings of the National Academy of Sciences (2004), pp. 13268-13272. [ pdf ]
Istrail, S., Sutton, G. G., Florea, L., Halpern, A. L., Mobarry, C. M., Lippert, R., Walenz, B., Shatkay, H., Dew, I., Miller, J. R., Flanigan, M. J., Edwards, N. J., Bolanos, R., Fasulo, D., Halldorsson, B. V., Hannenhalli, S., Turner, R., Yooseph, S., Lu, F., Nusskern, D. R., Shue, B. C., Zheng, X. H., Zhong, F., Delcher, A. L., Huson, D. H., Kravitz, S. A., Mouchard, L., Reinert, K., Remington, K. A., Clark, A. G., Waterman, M. S., Eichler, E. E., Adams, M. D., Hunkapiller, M. W., Myers, E. W., and Venter, J. C. Whole genome shotgun assembly and comparison of human assemblies. In Proceedings of the National Academy of Sciences (2004), pp. 1916-1921. [ pdf ]
Lippert, R., Zhao, X., Florea, L., Mobarry, C., and Istrail, S. Finding anchors for genomic sequence comparison. In Proceedings of the 8th Annual Conference on Research in Computational Biology (RECOMB04) (2004), ACM Press, pp. 233-241. [ pdf ]
2003
Bafna, V., Halldorsson, B. V., Schwartz, R. S., Clark, A. G., and Istrail, S. Haplotypes and informative SNP selection algorithms : don't block out information. In Proceedings of the 7th Annual Conference on Research in Computational Biology (RECOMB03) (2003), ACM Press, pp. 19-27. [ pdf ]
Florea, L., Halldorsson, B. V., Kohlbacher, O., Schwartz, R. S., Hoffman, S., and Istrail, S. Epitope prediction algorithms for peptide-based vaccine design. In Proceedings of the 2nd Annual IEEE Computer Society Bioinformatics Conference (CSB03) (2003), IEEE Press, pp. 17-26. [ pdf ]
Halldorsson, B. V., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., and Istrail, S. Combinatorial problems arising in SNP and haplotype analysis. In Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (CDMTCS03) (2003), Springer (Lecture Notes in Computer Science), pp. 26-47. [ pdf ]
Halldorsson, B. V., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., and Istrail, S. A survey of computational methods for determining haplotypes. In Proceedings of the 1st Research in Computational Biology (RECOMB) Satellite on Computational Methods for SNPs and Haplotype Inference (RECOMB SNP&HAP03) (2003), Springer (Lecture Notes in Bioinformatics), pp. 26-47. [ pdf ]
Lancia, G., and Istrail, S. Protein structure comparison: algorithms and applications, vol. 2666. Springer Verlag (Lecture Notes in Bioinformatics), 2003, pp. 1-33. [ pdf ]
Schwartz, R., Clark, A., and Istrail, S. Inferring piecewise ancestral sequences from haploid sequences. In Proceedings of the 1st Research in Computational Biology (RECOMB) Satellite on Computational Methods for SNPs and Haplotype Inference (RECOMB SNP&HAP03) (2003), Springer (Lecture Notes in Bioinformatics). [ pdf ]
Schwartz, R. S., Halldorsson, B. V., Bafna, V., Clark, A. G., and Istrail, S. Robustness of inference of haplotype block structure. Journal of Computational Biology 10 (2003), 13-19. [ pdf ]
2002
Lippert, R., Schwartz, R., Lancia, G., and Istrail, S. Algorithmic strategies for the SNP haplotype assembly problem. Briefings in Bioinformatics 3, 1 (Mar. 2002), 1-9. [ pdf ]
Istrail, S. The Haplotype Phasing Problem. Tech. rep., Celera Genomics, 2002.
Rizzi, R., Bafna, V., Istrail, S., and Lancia, G. Priactical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI02) (2002), Springer (Lecture Notes in Computer Science), pp. 29-43. [ pdf ]
Schwartz, R., Clark, A., and Istrail, S. Methods for inferring block-wise ancestral history from haploid sequences: The haplotype coloring problem. In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI02) (2002), Springer (Lecture Notes in Computer Science), pp. 44-59. [ pdf ]
2001
Turner, R., Chaturvedi, K., Edwards, N., Fasulo, D., Halpern, A., Huson, D., Kohlbacher, O., Miller, J., Reinert, K., Remington, K., Schwartz, R., Walenz, B., Yooseph, S., and Istrail, S. Visualization challenges for a new cyberpharmaceutical computing paradigm. In Proceedings of the Symposium on Large-Data Visualization and Graphics (San Diego, California, Oct. 2001), pp. 7-18. [ pdf ]
Lancia, G., Carr, R., Walenz, B., and Istrail, S. 101 Optimal PDB structure alignments: A branch-and-cut algorithm for the maximum contact map overlap problem. In Proceedings of the 5th Annual Conference on Research in Computational Biology (RECOMB01) (2001), ACM Press, pp. 201-211. [ pdf ]
Lancia, G., Bafna, V., Istrail, S., Lippert, R., and Schwartz, R. SNPs problems: complexity and algorithms. In Proceedings of the 3rd European Symposium on Algorithms (EAS01) (2001), Springer (Lecture Notes in Computer Science), pp. 182-193. [ pdf ]
Li, M., Lippert, R., Schwartz, R., Waterman, M., and Istrail, S. Haplotype reconstruction from SNP alignment. Tech. rep., Celera Genomics, 2001.
Schwartz, R., Istrail, S., and King, J. Frequencies of amino-acid strings in globular proteins sequences indicate suppression of blocks of consecutive hydrophobic residues. Protein Science 10 (2001), 1023-1031. [ pdf ]
Venter, J. C., Adams, M. D., Myers, E. W., Li, P., Mural, R. J., Sutton, G. G., Smith, H. O., Yandell, M., Evans, C. A., Holt, R. A., Gocayne, J. D., Amanatides, P., Ballew, R. M., Huson, D. H., Wortman, J. R., Zhang, Q., Kodira, C., Zheng, X. H., Chen, L., Skupski, M., Subramanian, G., Thomas, P. D., Zhang, J., Miklos, G. L. G., Nelson, C., Broder, S., Clark, A. G., Nadeau, J., McKusick, V. A., Zinder, N., Levine, A. J., Roberts, R. J., Simon, M., Slayman, C., Hunkapiller, M., Bolanos, R., Delcher, A., Dew, I., Fasulo, D., Flanigan, M., Florea, L., Halpern, A., Hannenhalli, S., Kravitz, S., Levy, S., Mobarry, C., Reinert, K., Remington, K., Abu-Threideh, J., Beasley, E., Biddick, K., Bonazzi, V., Brandon, R., Cargill, M., Chandramouliswaran, I., Charlab, R., Chaturvedi, K., Deng, Z., Francesco, V. D., Dunn, P., Eilbeck, K., Evangelista, C., Gabrielian, A. E., Gan, W., Ge, W., Gong, F., Gu, Z., Guan, P., Heiman, T. A., Higgins, M. E., Ji, R.-R., Ke, Z., Ketchum, K. A., Lai, Z., Lei, Y., Li, Z., Li, J., Liang, Y., Lin, X., Lu, F., Merkulov, G. V., Milshina, N., Moore, H. M., Naik, A. K., Narayan, V. A., Neelam, B., Nusskern, D., Rusch, D. B., Salzberg, S., Shao, W., Shue, B., Sun, J., Wang, Z. Y., Wang, A., Wang, X., Wang, J., Wei, M.-H., Wides, R., Xiao, C., Yan, C., Yao, A., Ye, J., Zhan, M., Zhang, W., Zhang, H., Zhao, Q., Zheng, L., Zhong, F., Zhong, W., Zhu, S. C., Zhao, S., Gilbert, D., Baumhueter, S., Spier, G., Carter, C., Cravchik, A., Woodage, T., Ali, F., An, H., Awe, A., Baldwin, D., Baden, H., Barnstead, M., Barrow, I., Beeson, K., Busam, D., Carver, A., Center, A., Cheng, M. L., Curry, L., Danaher, S., Davenport, L., Desilets, R., Dietz, S., Dodson, K., Doup, L., Ferriera, S., Garg, N., Gluecksmann, A., Hart, B., Haynes, J., Haynes, C., Heiner, C., Hladun, S., Hostin, D., Houck, J., a Chinyere Ibegwam, T. H., Johnson, J., Kalush, F., Kline, L., Koduru, S., Love, A., Mann, F., May, D., McCawley, S., McIntosh, T., McMullen, I., Moy, M., Moy, L., Murphy, B., Nelson, K., Pfannkoch, C., Pratts, E., Puri, V., Qureshi, H., Reardon, M., Rodriguez, R., Rogers, Y.-H., Romblad, D., Ruhfel, B., Scott, R., Sitter, C., Smallwood, M., Stewart, E., Strong, R., Suh, E., Thomas, R., Tint, N. N., Tse, S., Vech, C., Wang, G., Wetter, J., Williams, S., Williams, M., Windsor, S., Winn-Deen, E., Wolfe, K., Zaveri, J., Zaveri, K., Abril, J. F., Guigo, R., Campbell, M. J., Sjolander, K. V., Karlak, B., Kejariwal, A., Mi, H., Lazareva, B., Hatton, T., Narechania, A., Diemer, K., Muruganujan, A., Guo, N., Sato, S., Bafna, V., Istrail, S., Lippert, R., Schwartz, R., Walenz, B., Yooseph, S., Allen, D., B, A., Baxendale, J., Blick, L., Caminha, M., Carnes-Stine, J., Caulk, P., Chiang, Y.-H., Coyne, M., Dahlke, C., Mays, A. D., Dombroski, M., Donnelly, M., Ely, D., Esparham, S., Fosler, C., Gire, H., Glanowski, S., Glasser, K., Glodek, A., Gorokhov, M., Graham, K., Gropman, B., Harris, M., Heil, J., Henderson, S., Hoover, J., Jennings, D., Jordan, C., Jordan, J., Kasha, J., Kagan, L., Kraft, C., Levitsky, A., Lewis, M., Liu, X., Lopez, J., Ma, D., Majoros, W., McDaniel, J., Murphy, S., Newman, M., Nguyen, T., Nguyen, N., Nodell, M., Pan, S., Peck, J., Rowe, W., Sanders, R., Scott, J., Simpson, M., Smith, T., Sprague, A., Stockwell, T., Turner, R., Venter, E., Wang, M., Wen, M., Wu, D., Wu, M., Xia, A., Zandieh, A., and Zhu, X. The sequence of the human genome. Science 291 (2001), 1304-1351. [ pdf ]
2000
Istrail, S. Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intractability of the partition functions of the Ising model across non-planar lattices. In Proceedings of the 32nd ACM Symposium on the Theory of Computing (STOC00) (Portland, Oregon, May 2000), ACM Press, pp. 87-96. [ pdf ]
Batzoglou, S., and Istrail, S. Physical mapping with repeated probes: The hypergraph superstring problem. Journal of Discrete Algorithms 1 (2000), 51-76.
Goldman, D., Istrail, S., Lancia, G., Piccolboni, A., and Walenz, B. Algorithmic strategies in combinatorial chemistry. In Proceedings of the ACM/Society for Industrial and Applied Mathematics (SIAM) Symposium on Discrete Algorithms (SODA00) (Jan. 2000), ACM Press, pp. 275-284. [ pdf ]
1999
Goldman, D., Istrail, S., and Papadimitriou, C. Algorithms aspects of protein structure similarity. In Proceedings of the 40th Annual IEEE Symposium on the Foundations of Computer Science (FOCS99) (Oct. 1999), IEEE Computer Society Press. [ pdf ]
Batzoglou, S., and Istrail, S. Physical mapping with repeated probes: The hypergraph superstring problem. In Proceedings of the 10th Conference on Combinatorial Pattern Matching (CPM99) (Warwick, England, July 1999), Springer (Lecture Notes in Computer Science), pp. 66-77. [ pdf ]
Carr, B., Lancia, G., and Istrail, S. Branch-and-bound LP-algorithms for protein structure alignment based on contact map overlap. Tech. rep., Sandia National Laboratories, 1999.
Conway, J. H., and Istrail, S. Mathematics of self-assembly. Tech. rep., Sandia National Laboratories, 1999.
Istrail, S., Schwartz, R., and King, J. Lattice simulations of aggregation funnels of protein folding. Journal of Computational Biology 6, 2 (1999).
Lippert, R., Istrail, S., and Hurd, A. Prediction of energetic tiles self-assembly. Tech. rep., Sandia Labs, 1999.
Schwartz, R., Istrail, S., and King, J. Insights into the association of partially folded chains dervied from lattice simulation models. Tech. rep., Sandia National Laboratories, 1999.
1998
Istrail, S. Multiple Sequence Alignment and Voting Paradoxes. Tech. rep., 1998.
Istrail, S., and Ravi, R. What is a good objective for multiple sequence alignment. Tech. rep., Sandia National Laboratories, 1998.
1997
Hart, W. E., and Istrail, S. Lattice and off-lattice side chain models of protein folding: linear time structure prediction better than 86 percent of optimal (extended abstract). In Proceedings of the 1st Annual Conference on Research in Computational Biology (RECOMB97) (Jan. 1997), ACM Press, pp. 137-146. [ pdf ]
Hart, W. E., and Istrail, S. Robust proofs of NP-hardness for protein folding: general lattices and energy potentials. Journal of Computational Biology 4, 1 (1997), 1-22.
1996
Hart, W. E., and Istrail, S. Invariant patterns in crystal lattices: implications for protein folding algorithms. In Proceedings of the 7th Conference on Combinatorial Pattern Matching (CPM96) (June 1996), Springer (Lecture Notes in Computer Science), pp. 288-303. [ pdf ]
Hart, W. E., and Istrail, S. Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (extended abstract). Journal of Computational Biology 3, 1 (1996), 53-96.
1995
Bloom, B., Istrail, S., and Meyer, A. R. Bisimulation can't be traced. Journal of the ACM 42 (Jan. 1995), 232-268. [ pdf ]
Greenberg, D. S., and Istrail, S. Physical mapping by STS hybridization: algorithmic strategies and the challenge of software evaluation. Journal of Computational Biology 2, 2 (1995), 219-274. [ pdf ]
Hart, W. E., and Istrail, S. Crystallographical universal approximation: A complexity theory of protein folding algorithms for crystal lattices. Tech. rep., Sandia National Laboratories, 1995.
Hart, W. E., and Istrail, S. Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (extended abstract). In Proceedings of the 27nd ACM Symposium on the Theory of Computing (STOC95) (1995), ACM Press, pp. 157-168. [ pdf ]
1994
Greenberg, D. S., and Istrail, S. The chimeric mapping problem: algorithmic strategies and performance evaluation on synthetic genomic data. Computers and Chemistry 18, 3 (1994), 207-220.
Zivkoivic, D., and Istrail, S. Bounded-width polynomial size Boolean formulas compute exactly those functions from AC0. Information Processing Letters 50 (1994), 211-216.
1993
Istrail, S. The chimeric clones problem. Tech. rep., Sandia National Laboratories, 1993.
Zivkoivic, D., and Istrail, S. A non-probabilistic switching lemma for the Sipser function. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS93) (1993), Springer (Lecture Notes in Computer Science), pp. 566-575.
1992
Heath, L., and Istrail, S. The pagenumber of genus g graphs is O(g). ACM Press 39 (1992), 479-501.
1991
Zipoli, J., and Istrail, S. On the impossibility of the crossover method for proving NP-completeness of the planar chromatic index problem. Tech. rep., Wesleyan University, 1991.
1990
Istrail, S. Constructing generalized universal traversal sequences of polynomial size for graphs of small diameter. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science (FOCS90) (1990), IEEE Computer Society Press, pp. 439-448. [ pdf ]
Istrail, S. On the complexity of unpredictability. Tech. rep., Wesleyan University, 1990.
1989
Istrail, S. An arithmetical hierarchy in propositional dynamic logic. Information and Computation 81, 3 (1989), 280-289.
1988
Bloom, B., Istrail, S., and Meyer, A. R. Bisimulation can't be traced. In Proceedings of the 15th Annual ACM Symposium on Principles of Programming Languages (POPL88) (1988), ACM Press, pp. 229-239. [ pdf ]
Istrail, S. An algorithm for embedding planar graphs in six pages. Iasi University Annals, Mathematics-Computer Science 34, 4 (1988), 329-341.
Istrail, S. Polynomial universal traversal sequences for cycles are constructible. In Proceedings of the 20th ACM Symposium on the Theory of Computing (STOC88) (1988), ACM Press, pp. 491-453. [ pdf ]
1987
Heath, L., and Istrail, S. The pagenumber of genus g graphs is O(g). In Proceedings of the 19th ACM Symposium on the Theory of Computing (STOC87) (1987), ACM Press, pp. 388-397.
1983
Istrail, S. A programming exercise with some theoretical appeal, Part I and Part II. In Bulletin of the European Association for Theoretical Computer Science. 1983, pp. 70-97.
Masalagiu, C., and Istrail, S. Nivat's processing systems: decision problems related to protection and synchronization. Theoretical Computer Science 26 (1983), 83-103.
Masalagiu, C., and Istrail, S. On protection in Nivat processing systems. In Proceedings of the Colloqium on Automata and Programming (CAAP83) (New York, 1983), Springer (Lecture Notes in Computer Science), pp. 255-268.
1982
Istrail, S. Generalizations of Ginsburg-Rice-Schutzenberger fixed-point theorem for context-sensitive and recursive-enumerable sets. Theoretical Computer Science 18 (1982), 333-341.
Istrail, S. Some remarks on non-algebraic adherences. Theoretical Computer Science 21 (1982), 341-349.
My, N. X., and Istrail, S. N-contextual schemes. Bulletin Mathematique 26, 3 (1982), 241-249.
Olaru, L., and Istrail, S. Pictorial grammars: models for the syntax of the patterns of folk art textures. In The Mathematical Semiotics of Visual Arts, E. S. s. E. S Marcus, Ed. Bucharest, 1982, pp. 221-256.
1981
Istrail, S. On the scientific activity of Laurent Chottin (1947-1979). In Bulletin of the European Association for Theoretical Computer Science. Oct. 1981, pp. 139-146.
Istrail, S. Chomsky-Schutzenberger representations for families of languages and grammatical types. In Proceedings of the International Conference on Automata, Languages and Programming (ICALP81) (New York, 1981), Springer (Lecture Notes in Computer Science), pp. 333-347.
Istrail, S. On a linear theory of recursive-enumerable sets. Series in Mathematics 22, 38 (1981).
Masalagiu, C., and Istrail, S. Decision problems for languages associated with protection of systems. Automatic Systems and Informatics (1981), 306-312.
1980
Istrail, S. A fixed-point approach to contextual languages. Revue Roumaine de Mathematiques Pures et Appliquees 25, 6 (1980), 861-869.
Olaru, L., and Istrail, S. An efficient data structure for computer graphics. Artificial Intelligence and Information Control Systems of Robots (1980), 83-85.
1979
Istrail, S. On the complexity of program divergence. Foundations of Control Engineering 4, 1 (1979), 19-26.
Istrail, S. On complements of some bounded context-sensitive languages. Information and Control 42, 3 (1979), 283-289.
Istrail, S. A fixed-point theorem for recursive-enumerable languages and some considerations about semantics of monadic programs. In Proceedings of the International Conference on Automata, Languages and Programming (ICALP79) (New York, 1979), Springer (Lecture Notes in Computer Science), pp. 289-303.
1978
Istrail, S., and Simovici, D. Computing grammars and context-sensitive languages. Revue Francais D'Automatique Informatique et Recherche Operationelle 12, 1 (1978), 33-48.
Istrail, S. Contextual grammars with regular choice. Studii si Cercetari Matematice 30, 3 (1978), 287-294.
Istrail, S. Elementary bounded languages. Information and Control 39, 2 (1978), 177-191.
Istrail, S. A problem about contextual grammars with choice. Studii si Cercetari Matematice 30, 4 (1978), 401-408.
1977
Istrail, S. On formal constructions of algebraic numbers of degree two. Revue Roumaine de Mathematiques Pures et Appliquees 22, 9 (1977), 1235-1239.
Istrail, S. On irreducible languages and nonrational numbers. Bulletin Mathematique 21, 3-4 (1977), 301-308.
Istrail, S. On the weak equivalence problem of OL-systems with some generative devices. Iasi University Annals 23, 2 (1977), 419-422.
1976
Istrail, S. On some symmetric operators on free semigroups. Studii si Cercetari Matematice 28, 1 (1976), 111-121.
| Page Owner: Sorin Istrail | Last Modified: Tue Sep 8 19:51:04 2009 |