Publications

Under Construction. The online papers here are pre-publication draft versions. This page and the summary chart are automatically generated by a script that parses a bibtex file. If you notice any errors, please let me know.
Last regenerated on Tue Jan 10 00:24:30 PST 2006

2006

• Structural alignment of pseudoknotted RNA
  B. Dost, B. Han, S. Zhang, and V. Bafna
  RECOMB, 2006
  We compute a structural alignment of an RNA sequence with a complex pseudo-knotted secondary structure against genomic DNA. The alignment can be used to mine genomes for pseudoknotted ncRNA.

2005

• Identification of post-translational modifications by blind search of mass spectra
  D. Tsur, S. Tanner, E. Zandi, V. Bafna, and P.A. Pevzner
  Nat. Biotech., 2005 23(12):1562--1567.
  
  We reliably identify PT modifications/mutations from Tandem Mass Spectra in a blind fashion. (prelim. version) .
• Peptide sequence tags for fast database search in mass-spectrometry
  A. Frank, S. Tanner, V. Bafna, and P.A. Pevzner
  J Proteome Res, 2005 4(4):1287--1295.
  
  More results on efficient genome filtering using de novo analysis.
• Orthologous Repeats and Mammalian Phylogenetic Inference
  Ali Bashir, Chun Ye, Alkes Price, and Vineet Bafna
  Genome Research, 2005 15(7):998--1006.
  
  Can transposon repeats be used as markers for phylogeny reconstruction? The answer is yes, at least for mammals. pdf .
• Identification of Post-translational Modifications via Blind Search of Mass-Spectra
  Tsur, D., Tanner, S., Zandi, E., Bafna, V., and Pevzner, P.A.
  Proceedings of IEEE Computational Systems Bioinformatics (CSB) Conference, 2005 :157-166.
  
  We reliably identify post-translational modifications and mutations with no prior knowledge of possiblities. See improved version in the Nat. Biotech. paper.
• InsPecT: identification of posttranslationally modified peptides from tandem mass spectra
  S. Tanner, H. Shu, A. Frank, L. Wang, E. Zandi, M. Mumby, P.A. Pevzner, and V. Bafna
  Anal Chem, 2005 77(14):4626--4639.
  
  Can you quickly, and reliably, identify post-translationally modified peptides given their Tandem Mass Spectra? Yes, using a mix of de novo analysis, trie based filtering, and careful scoring. ( (pdf) ).InsPecT can't do a blind search for modifications however, but see CSB2005, and Nat. Biotech. 2005.
• Consensus folding of unaligned RNA sequences revisited
  Vineet Bafna, Haixu Tang, and Shaojie Zhang
  RECOMB, 2005 :172--187.
  
  The problem is well studied, but most methods show either poor sensitivity, or specificity. We improve the state of the art by computing anchored structures, and combined sequence structure alignment. (pdf) .
• Improved Recombination Lower Bounds for Haplotype Data
  Vineet Bafna and Vikas Bansal
  RECOMB, 2005 :569--584.
  
  We show that the Myers & Griffiths lower bounds are NP-complete, and provide efficient and improved lower bounds. The bounds are applied to study fine-scale changes in recombination rate. ( Preliminary version )
• Mass Spectrometry and Computational Proteomics
  Vineet Bafna and Knut Reinert
  Encyclopedia of Genetics, Genomics, Proteomics and Bioinformatics, 2005
  A lot has changed since this survey was written, particularly the combined use of de novo analysis and database searching for peptide identification. ( pdf ).
• Polynomial and APX-hard cases of Individual Haplotyping Problems
  Vineet Bafna, Sorin Istrail, Giuseppe Lancia, and Romeo Rizzi
  Theoretical Computer Science, 2005 335(1):109--125.
  
  Haplotyping would be much easier if we could sequence long stretches of sequence. This paper explores some of the possibilities. ( pdf) .

2004

• Orthologous Repeats and Phylogenetic Inference
  Ali Bashir, Chun Ye, Alkes Price, and Vineet Bafna
  RECOMB Satellite workshop on Comparative Genomics, 2004
  Can transposon repeats be used as markers for phylogeny reconstruction? The answer is yes, at least for mammals. The prelim. results presented here have been greatly improved for a journal submission. (pdf) .
• Shotgun Sequencing by tandem mass spectra assembly
  Nuno Bandeira, Haixu Tang, Vineet Bafna, and Pavel Pevzner
  Analytical Chemistry, 2004 76(24):7221-33.
  
  The paper gives a framework for de novo sequencing of protein sequences using non-specific digestion and Tandem MS. (pdf) .
• FastR: Fast database search tool for non-coding RNA
  Vineet Bafna and Shaojie Zhang
  Proceedings of IEEE Computational Systems Bioinformatics (CSB) Conference, 2004 :52-61.
  
  We describe a BLAST like tool for ncRNA. The main idea is the use of structural filters which efficiently eliminate much of the database, while retaining true homologs. ( pdf ).
• Optimal haplotype block free selection of tagging SNPs for genome-wide association studies
  Bjarni V. Halld\'orsson, Vineet Bafna, Ross Lippert, Russell Schwartz, Frasisco M. De La Vega, Andrew G. Clark, and Sorin Istrail
  Genome Research, 2004 14:1633-1640.
  
  We show that the notion of blocks is robust, but not the notion of exact block boundaries. Next, we describe a novel approach to SNP tagging which does not rely on a prior decomposition into haplotype blocks. ( pdf ).
• A note on efficient computation of haplotypes via perfect phylogeny
  Vineet Bafna, Dan Gusfield, Sridhar Hannenhalli, and Shibu Yooseph
  Journal of Computational Biology, 2004 11(5):858--866.
  
  Some simple hardness results on perfect phylogeny haplotyping. ( pdf ).
• The Number of Recombination events in a Sample History:Conflict graph and lower bounds
  Vineet Bafna and Vikas Bansal
  IEEE/ACM Transactions on Computational Biology, 2004 1(2):78--90.
  
  We show that the number of connected components in the conflict graph is a lower bound on the number of recombinations. Surprisingly, the bounds can sometimes be better than the $R_h$ bound of Myers and Griffiths, which are much harder to compute. ( pdf ).

2003

• The Dog Genome: Survey Sequencing and Comparative Analysis
  Ewen F. Kirkness, Vineet Bafna, Aaron L. Halpern, Samuel Levy, Karin Remington, Douglas B. Rusch, Arthur L. Delcher, Mihai Pop, Wei Wang, Claire M. Fraser, and J. Craig Venter
  Science, 2003 301(5641):1898-903.
  
  The paper describes the cost benefit tradeoffs of low coverage (1.5X) shotgun sequencing.
• Combinatorial Problems arising in SNP and Haplotype Analysis
  Bjarni V. Halld\'orsson, Vineet Bafna, Nathan Edwards, Ross Lippert, Shibu Yooseph, and Sorin Istrail
  DMTCS, 2003 :26-47.
  
• Robustness of Inference of Haplotype Block Structure
  R. S. Schwartz, B. V. Halld\'orsson, V. Bafna, A. G. Clark, and S. Istrail
  jcb, 2003 10(1):13-20.
  
  ( pdf ).
• Haplotyping as Perfect Phylogeny: A Direct Approach
  V. Bafna, D. Gusfield, G. Lancia, and S. Yooseph
  Journal of Computational Biology, 2003 10(3):323-340.
  
  In regions with no recombination, the haplotypes have a perfect phylogeny. Can genotype data be phased so that the resulting haplotypes have a perfect phylogeny, if possible. This paper simplifies an earlier algorithm of Gusfield. (pdf) .
• On de novo interpretation of peptide mass spectra
  Vineet Bafna and Nathan Edwards
  RECOMB, 2003 :9-18.
  
  Extends a forbidden pairs DP to multiple ion types. ( pdf ).
• Haplotypes and Informative SNP selection: Don't block out information
  V. Bafna, B. V. Halldorsson, R. Schwartz, A. Clark, and S. Istrail
  RECOMB, 2003 :19-27.
  
  We describe a Block free SNP tagging algorithm. (pdf) .

before 2002

• Practical Algorithms and Fixed-Parameter tractability for
  R. Rizzi, V. Bafna, S. Istrail, and G. Lancia
  Proceedings 2nd Workshop on Algorithms in Bioinformatics, 2002 :29-43.
  
  ( pdf ).
• Algorithms for High-throughput Comparison of Peptide
  Vineet Bafna, Oliver Kohlbacher, Knut Reinert, Shibu Yooseph, and Scott Patterson
  , 2002
• SCOPE: a probabilistic model for scoring tandem mass spectra against a peptide database
  Vineet Bafna and Nathan Edwards
  bix, 2001 17 Suppl 1:S13-21.
  
  (pdf .
• Circular Permutations and Gene Shuffling
  Vineet Bafna, Donald Beaver, and Martin F\
  Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families, 2001
• et al. The sequence of the human genome
  Craig Venter
  Science, 2001 291(5507):1304-51.
  
• SNPs Problems, Complexity, and Algorithms
  Giuseppe Lancia, Vineet Bafna, Sorin Istrail, Ross Lippert, and Russell Schwartz
  European Symposium on Algorithms (ESA), 2001 :182-193.
  
  ( pdf ).
• The conserved exon method for gene finding
  Vineet Bafna and Daniel Huson
  ISMB, 2000 8:3-12.
  
• Ligand-receptor pairing via tree comparison
  Vineet Bafna, Sridhar Hannenhalli, Ken Rice, and Lisa Vawter
  jcb, 2000 7(1-2):59-70.
  
• On the Approximability of Numerical Taxonomy (Fitting
  Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup
  sicomp, 1999 28(3):1073-1085.
  
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
  Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, and Chuan Yi Tang
  sicomp, 1999 29(3):761-778.
  
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
  Vineet Bafna, Piotr Berman, and Toshihiro Fujito
  SIAM Journal on Discrete Mathematics, 1999 12(3):289-297.
  
• The Ribosome scanning model for translation initiation: implications for gene prediction and full-length cDNA detection
  Pankaj Agarwal and Vineet Bafna
  ISMB, 1998 6:2-7.
  
• Human beta-defensin 2 is a salt-sensitive peptide antibiotic expressed in human lung
  R. Bals, X. Wang, Z. Wu, T. Freeman, V. Bafna, M. Zasloff, and J.M. Wilson
  Journal of Clinical Investigation, 1998 102(5):874-80.
  
• Detecting non-adjoining correlations with signals in DNA
  Pankaj K. Agarwal and Vineet Bafna
  RECOMB, 1998 :2-8.
  
• Sorting by Transpositions
  Vineet Bafna and Pavel A. Pevzner
  SIAM Journal on Discrete Mathematics, 1998 11(2):224-240.
  
• Approximation Algorithms for Multiple Sequence Alignment
  Vineet Bafna, Eugene L. Lawler, and Pavel A. Pevzner
  tcs, 1997 182(1-2):233-244.
  
• On the Approximability of Numerical Taxonomy
  Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup
  SODA, 1996 :365-372.
  
• Genome Rearrangements and Sorting by Reversals
  Vineet Bafna and Pavel A. Pevzner
  sicomp, 1996 25(2):272-289.
  
• Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs
  Vineet Bafna, Piotr Berman, and Toshihiro Fujito
  ISAAC 95 Algorithms and Computation, 1995 1004:142-151.
  
• Computing similarity in RNA strings
  Vineet Bafna, S. Muthukrishnan, and R. Ravi
  6th Annual Symposium on Combinatorial Pattern Matching, 1995 937:1-16.
  
• Non-overlapping local alignments
  Vineet Bafna, Babu Narayanan, and R. Ravi
  Workshop on Algorithms and Data Structures, 1995 955:506-517.
  
• Sorting Permutations by Transpositions
  Vineet Bafna and Pavel A. Pevzner
  SODA, 1995 :614-623.
  
• Sorting by reversals: Genome rearrangements in plant organelles and evolutionary history of X chromosome
  Vineet Bafna and Pavel A. Pevzner
  Molecular Biology and Evolution, 1995 12:239-246.
  
• Genome Rearrangements and Sorting by Reversals
  Vineet Bafna and Pavel A. Pevzner
  FOCS, 1994 :148-157.
  
• Approximation Algorithms for Multiple Sequence Alignment
  Vineet Bafna, Eugene L. Lawler, and Pavel A. Pevzner
  CPM, 1994
• Not all insertion methods yield constant approximate tours
  Vineet Bafna, B. Kalyanasundaram, and K. Pruhs
  Theoretical Computer Science, 1992