Publications

Publications, organized by subject. Also available are abstracts, and links to collaborators.

John has an Erdös number of three, by the path
Kececioglu, Sankoff, Chvátal, Erdös.

Subjects

• Inverse alignment
• Multiple alignment
• Sequence assembly


• Physical mapping
• Genome rearrangement
• Recombinations


• Biology
• Matchings
• Systems

Inverse alignment

• "Learning models for aligning protein sequences with predicted secondary structure,"
  Eagu Kim, Travis Wheeler and John Kececioglu,
  Proceedings of the 13th Conference on Research in Computational Molecular Biology (RECOMB), to appear 2009.


• "Learning scoring schemes for sequence alignment from partial examples,"
  Eagu Kim and John Kececioglu,
  IEEE/ACM Transactions on Computational Biology and Bioinformatics 5:4, 546-556, 2008.
  


• "Inverse sequence alignment from partial examples,"
  Eagu Kim and John Kececioglu,
  Proceedings of the 7th EATCS/ISCB Workshop on Algorithms in Bioinformatics (WABI), Springer-Verlag Lecture Notes in Bioinformatics 4645, 359-370, 2007.
  

  Software implementing the algorithm in this paper is available at inversealign.cs.arizona.edu.

• "Simple and fast inverse alignment,"
  John Kececioglu and Eagu Kim,
  Proceedings of the 10th ACM Conference on Research in Computational Molecular Biology (RECOMB), 441-455, 2006.

Multiple alignment

• "Multiple alignment by aligning alignments,"
  Travis Wheeler and John Kececioglu,
  Proceedings of the 15th ISCB Conference on Intelligent Systems for Molecular Biology (ISMB), Bioinformatics 23, i559-i568, 2007.
  

  The conference talk presenting this paper is available here. Software implementing the algorithm in this paper is available at opal.cs.arizona.edu.

• "Aligning alignments exactly,"
  John Kececioglu and Dean Starrett,
  Proceedings of the 8th ACM Conference on Research in Computational Molecular Biology (RECOMB), 85-96, 2004.

  Software implementing the algorithm in this paper is available at alignalign.cs.arizona.edu.

• "A polyhedral approach to sequence alignment problems,"
  John Kececioglu, Hans-Peter Lenhof, Kurt Mehlhorn, Petra Mutzel, Knut Reinert and Martin Vingron,
  Discrete Applied Mathematics 104, 143-186, 2000.
  

  An earlier version appeared as K. Reinert, H.-P. Lenhof, P. Mutzel, K. Mehlhorn and J. Kececioglu, "A branch-and-cut algorithm for multiple sequence alignment," Proceedings of the 1st ACM Conference on Research in Computational Molecular Biology (RECOMB), 241-249, 1997.

• "Aligning alignments,"
  John Kececioglu and Weiqing Zhang,
  Proceedings of the 9th Symposium on Combinatorial Pattern Matching (CPM), Springer-Verlag Lecture Notes in Computer Science 1448, 189-208, 1998.
  


• "Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree,"
  R. Ravi and John Kececioglu,
  Discrete Applied Mathematics 88, 355-366, 1998.
  

  An earlier version appeared as R. Ravi and J. Kececioglu, "Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree," Proceedings of the 6th Symposium on Combinatorial Pattern Matching (CPM), Springer-Verlag Lecture Notes in Computer Science 937, 330-339, 1995.

• "Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment,"
  Sandeep Gupta, John Kececioglu and Alejandro Schäffer,
  Journal of Computational Biology 2:3, 459-472, 1995.
  

  An earlier version appeared as S. Gupta, J. Kececioglu and A. Schäffer, "Making the shortest-paths approach to sum-of-pairs multiple sequence alignment more space efficient in practice," Proceedings of the 6th Symposium on Combinatorial Pattern Matching (CPM), Springer-Verlag Lecture Notes in Computer Science 937, 128-43, 1995.

• "The maximum weight trace problem in multiple sequence alignment,"
  John Kececioglu,
  Proceedings of the 4th Symposium on Combinatorial Pattern Matching (CPM), Springer-Verlag Lecture Notes in Computer Science 684, 106-119, 1993.


• "A tool for multiple sequence alignment,"
  David Lipman, Stephen Altschul and John Kececioglu,
  Proceedings of the National Academy of Science USA 86, 4412-4415, 1989.

Sequence assembly

• "Separating repeats in DNA sequence assembly,"
  John Kececioglu and Jun Yu,
  Proceedings of the 5th ACM Conference on Research in Computational Molecular Biology (RECOMB), 176-183, 2001.


• "Inferring a DNA sequence from erroneous copies,"
  John Kececioglu, Ming Li and John Tromp,
  Theoretical Computer Science 185:1, 3-13, 1997.
  


• "Combinatorial algorithms for DNA sequence assembly,"
  John Kececioglu and Eugene Myers,
  Algorithmica 13:1/2, 7-51, 1995.
  


• Exact and Approximation Algorithms for DNA Sequence Reconstruction,
  John Kececioglu,
  PhD dissertation, Technical Report 91-26, Department of Computer Science, University of Arizona, December 1991.

Physical mapping

• "Reconstructing distances in physical maps of chromosomes with nonoverlapping probes,"
  John Kececioglu, Sanjay Shete and Jonathan Arnold,
  Proceedings of the 4th ACM Conference on Research in Computational Molecular Biology (RECOMB), 183-192, 2000.


• "Computing physical maps of chromosomes with nonoverlapping probes by branch-and-cut,"
  Thomas Christof and John Kececioglu,
  Proceedings of the 3rd ACM Conference on Research in Computational Molecular Biology (RECOMB), 115-123, 1999.


• "A branch-and-cut approach to physical mapping of chromosomes by unique end-probes,"
  Thomas Christof, Michael Jünger, John Kececioglu, Petra Mutzel and Gerhard Reinelt,
  Journal of Computational Biology 4:4, 433-447, 1997.
  

  An earlier version appeared as T. Christof, M. Jünger, J. Kececioglu, P. Mutzel, and G. Reinelt, "A branch-and-cut approach to physical mapping with end-probes," Proceedings of the 1st ACM Conference on Research in Computational Molecular Biology (RECOMB), 84-92, 1997.

Genome rearrangement

• "Steiner points in the space of genome rearrangements,"
  David Sankoff, Gopal Sundaram and John Kececioglu,
  International Journal of Foundations of Computer Science 7:1, 1-9, 1996.
  


• "Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement,"
  John Kececioglu and David Sankoff,
  Algorithmica 13:1/2, 180-210, 1995.
  

  An earlier version appeared as J. Kececioglu and D. Sankoff, "Exact and approximation algorithms for the inversion distance between two chromosomes," Proceedings of the 4th Symposium on Combinatorial Pattern Matching (CPM), Springer-Verlag Lecture Notes in Computer Science 684, 87-105, 1993.

• "Of mice and men: Algorithms for evolutionary distances between genomes with translocation,"
  John Kececioglu and R. Ravi,
  Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 604-613, 1995.
  


• "Efficient bounds for oriented chromosome-inversion distance,"
  John Kececioglu and David Sankoff,
  Proceedings of the 5th Symposium on Combinatorial Pattern Matching (CPM), Springer-Verlag Lecture Notes in Computer Science 807, 307-325, 1994.

Recombinations

• "Reconstructing a history of recombinations from a set of sequences,"
  John Kececioglu and Dan Gusfield,
  Discrete Applied Mathematics 88, 239-260, 1998.
  

  An earlier version appeared as J. Kececioglu and D. Gusfield, "Reconstructing a history of recombinations from a set of sequences," Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), 471-480, 1994.

Biology

• "HIV-1 encodes a sequence overlapping env gp41 with highly significant similarity to selenium-dependent glutathione peroxidases,"
  Ethan Will Taylor, Ajita Bhat, Ram Nadimpalli, Weiqing Zhang and John Kececioglu,
  Journal of Acquired Immune Deficiency Syndromes and Human Retrovirology 15:5, 393-394, 1997.
  


• "Assessing distant homology between an aligned family and a proposed member through accurate sequence alignment,"
  Weiqing Zhang, John Kececioglu and Ethan Will Taylor,
  Technical Report 97-3, Department of Computer Science, University of Georgia, August 1997.

Matchings

• "Computing maximum-cardinality matchings in sparse general graphs,"
  John Kececioglu and Justin Pecqueur,
  Proceedings of the 2nd Workshop on Algorithm Engineering (WAE), 121-132, 1998.

Systems

• "Dynamic path-based software watermarking,"
  Christian Collberg, Edward Carter, Saumya Debray, Andrew Huntwork, John Kececioglu, Cullen Linn and Martin Stepp,
  Proceedings of the 25th ACM Conference on Programmming Language Design and Implementation (PLDI), 107-118, 2004.


• "Enhancing software tamper-resistance via stealthy address computations,"
  Cullen Linn, Saumya Debray and John Kececioglu,
  Presented as work in progress at the 19th Computer Security Applications Conference (CSA), 2003.

Reviews

• Review of Sequence Analysis Primer,
  Michael Gribskov and John Devereux editors, Stockton Press, New York, 1991;
  John Kececioglu,
  Journal of Classification 10, 144-148, 1993.

Collaborators

• Jonathan Arnold
• Thomas Christof
• Christian Collberg
• Saumya Debray
• Dan Gusfield
• Michael Jünger
• Hans-Peter Lenhof
• Ming Li
• Kurt Mehlhorn
• Petra Mutzel
• Gene Myers
• Ramamoorthi Ravi
• Gerhard Reinelt
• Knut Reinert
• David Sankoff
• Alex Schäffer
• Will Taylor
• John Tromp
• Martin Vingron