Ali Bashir, Chun Ye, Alkes L. Price, Vineet Bafna, Email Alerting, Ali Bashir, ...
data
Bjarni V. Halldórsson, Vineet Bafna, Russell Schwartz, Andrew G. Clark, Sorin Istrail
It is widely hoped that the study of sequence variation in the human genome will provide a means of elucidating the genetic component of complex diseases and variable drug responses. A major...
McKernan, Kevin Judd, Peckham, Heather E., Costa, Gina L., McLaughlin, Stephen F., Fu, Yutao, Tsung, Eric F., ...
We describe the genome sequencing of an anonymous individual of African origin using a novel ligation-based sequencing assay that enables a unique form of error correction that improves the raw...
The diploid genome sequence of an individual human (2008)
Samuel Levy, Granger Sutton, Pauline C. Ng, Lars Feuk, Aaron L. Halpern, Brian P. Walenz, ...
Presented here is a genome sequence of an individual human. It was produced from;32 million random DNA fragments, sequenced by Sanger dideoxy technology and assembled into 4,528 scaffolds, comprising...
Running Head: A Decomposition Theory for Phylogenetic Networks ∗ Corresponding Author: (2008)
Dan Gusfield, Vikas Bansal, Vineet Bafna, Yun S. Song, Dan Gusfield
1 Phylogenetic networks are models of evolution that go beyond trees, incorporating non-tree-like biological events such as recombination (or more generally reticulation), which occur either in a...
The Number of Recombination Events in a Sample History: Conflict Graph (2008)
Lower Bounds, Vineet Bafna, Vikas Bansal
Abstract—We consider the following problem: Given a set of binary sequences, determine lower bounds on the minimum number of recombinations required to explain the history of the sample, under the...
Shaojie Zhang, Ilya Borovok, Yair Aharonowitz, Roded Sharan, Vineet Bafna
doi:10.1093/bioinformatics/btl232 A sequence-based filtering method for ncRNA identification
Fast and Accurate Alignment of Multiple Protein Networks (2008)
Maxim Kalaev, Vineet Bafna, Roded Sharan
Abstract. Comparative analysis of protein networks has proven to be a powerful approach for elucidating network structure and predicting protein function and interaction. A fundamental challenge for...
Ali Bashir, Chun Ye, Alkes L. Price, Vineet Bafna, Email Alerting, Ali Bashir, ...
data
Nitin Gupta, Jamal Benhamida, Vipul Bhargava, Daniel Goodman, Elisabeth Kain, Ian Kerman, ...
Mass spectrometry recently emerged as a valuable technique for proteogenomic annotations that improve on the state-of-the art in predicting genes and other features. However, previous proteogenomic...
The diploid genome sequence of an individual human (2008)
Samuel Levy, Granger Sutton, Pauline C. Ng, Lars Feuk, Aaron L. Halpern, Brian P. Walenz, ...
Presented here is a genome sequence of an individual human. It was produced from;32 million random DNA fragments, sequenced by Sanger dideoxy technology and assembled into 4,528 scaffolds, comprising...
Marc Mumby, Pavel A. Pevzner, Vineet Bafna
Reliable identification of post-translational modifications is key to understanding various cellular regulatory processes. We describe a tool, InsPecT, to identify post-translational modifications...
Orthologous Repeats and Phylogenetic Inference (2008)
Ali Bashir, Chun Ye, Alkes Price, Vineet Bafna
Determining phylogenetic relationships between species is a difficult problem, and many phylogenetic relationships remain unresolved, even among eutherian mammals. Repetitive elements provide...
Three Algorithmic Problems (2008)
Vineet Bafna, Ari Frank, Pavel Pevzner, Stephen Tanner, Dekel Tsur, Pavel Pevzner
� Searching for a million words in a text. Suppose it takes 1 sec to find a word in a text. How much time would it take to find 1 million words in the text? � Searching for a word without even...
An MCMC algorithm for haplotype assembly from whole-genome sequence data (2008)
Bansal, Vikas, Halpern, Aaron L., Axelrod, Nelson, Bafna, Vineet
In comparison to genotypes, knowledge about haplotypes (the combination of alleles present on a single chromosome) is much more useful for whole-genome association studies and for making inferences...
Gupta, Nitin, Benhamida, Jamal, Bhargava, Vipul, Goodman, Daniel, Kain, Elisabeth, Kerman, Ian, ...
Recent proliferation of low-cost DNA sequencing techniques will soon lead to an explosive growth in the number of sequenced genomes and will turn manual annotations into a luxury. Mass spectrometry...
Vineet Bafna, Toshihiro Fujito
We consider the weighted feedback vertex set problem for undirected graphs. It is shown that a generalized local ratio strategy leads to an efficient approximation with the performance guarantee of...
Vineet Bafna, S. Muthukrishnan, R. Ravi
Ribonucleic acid (RNA) strings are strings over the four-letter alphabet fA; C; G;Ug with a secondary structure of base-pairing between A0U and C 0 G pairs in the string 1. Edges are drawn between...
The Diploid Genome Sequence of an Individual Human (2007)
Samuel Levy, Granger Sutton, Pauline C. Ng, Lars Feuk, Aaron L. Halpern, Brian P. Walenz, ...
Presented here is a genome sequence of an individual human. It was produced from ∼32 million random DNA fragments, sequenced by Sanger dideoxy technology and assembled into 4,528 scaffolds,...
Gupta, Nitin, Tanner, Stephen, Jaitly, Navdeep, Adkins, Joshua N., Lipton, Mary, Edwards, Robert, ...
While bacterial genome annotations have significantly improved in recent years, techniques for bacterial proteome annotation (including post-translational chemical modifications, signal peptides,...
The Sorcerer II Global Ocean Sampling Expedition: Expanding the Universe of Protein Families (2007)
Shibu Yooseph, Granger Sutton, Douglas B. Rusch, Aaron L. Halpern, Shannon J. Williamson, Karin Remington, ...
Metagenomics projects based on shotgun sequencing of populations of micro-organisms yield insight into protein families. We used sequence similarity clustering to explore proteins with a...
Improving gene annotation using peptide mass spectrometry (2007)
Tanner, Stephen, Shen, Zhouxin, Ng, Julio, Florea, Liliana, Guigó, Roderic, Briggs, Steven P, ...
Annotation of protein-coding genes is a key goal of genome sequencing projects. In spite of tremendous recent advances in computational gene finding, comprehensive annotation remains a challenge....
QNet: A tool for querying protein interaction networks (2007)
Banu Dost, Tomer Shlomi, Nitin Gupta, Vineet Bafna, Roded Sharan
Abstract. Molecular interaction databases can be used to study the evolution of molecular pathways across species. Querying such pathways is a challenging computational problem, and recent efforts...
The Sorcerer II global ocean sampling expedition: expanding the universe of protein families (2007)
Shibu Yooseph, Granger Sutton, Douglas B. Rusch, Aaron L. Halpern, Shannon J. Williamson, Karin Remington, ...
Metagenomics projects based on shotgun sequencing of populations of micro-organisms yield insight into protein families. We used sequence similarity clustering to explore proteins with a...
Improving gene annotation using peptide mass spectrometry (2007)
Tanner, Stephen, Shen, Zhouxin, Ng, Julio, Florea, Liliana, Guigó, Roderic, Briggs, Steven P., ...
Annotation of protein-coding genes is a key goal of genome sequencing projects. In spite of tremendous recent advances in computational gene finding, comprehensive annotation remains a challenge....
Optimization of primer design for the detection of variable genomic lesions in cancer (2007)
Bashir, Ali, Liu, Yu-Tsueng, Raphael, Benjamin J., Carson, Dennis, Bafna, Vineet
Primer approximation multiplex PCR (PAMP) is a new experimental protocol for efficiently assaying structural variation in genomes. PAMP is particularly suited to cancer genomes where the precise...
The Sorcerer II Global Ocean Sampling Expedition: Expanding the Universe of Protein Families (2006)
Yooseph, Shibu, Sutton, Granger, Rusch, Douglas B., Halpern, Aaron L., Williamson, Shannon J., Remington, Karin, ...
Structural alignment of pseudoknotted RNA (2006)
Banu Dost, Buhm Han, Shaojie Zhang, Vineet Bafna
Abstract. In this paper, we address the problem of discovering novel non-coding RNA (ncRNA) using primary sequence, and secondary structure conservation, focusing on ncRNA families with...
Shaojie Zhang, Ilya Borovok, Yair Aharonowitz, Roded Sharan, Vineet Bafna
Recent studies have uncovered an “RNA world”, in which non coding RNA (ncRNA) sequences play a central role in the regulation of gene expression. Computational studies on ncRNA have been directed...
Improving gene annotation using peptide mass spectrometry (2006)
Tanner, Stephen, Shen, Zhouxin, Ng, Julio, Florea, Liliana, Guigó, Roderic, Briggs, Steven P., ...
Annotation of protein-coding genes is a key goal of genome sequencing projects. In spite of tremendous recent advances in computational gene finding, comprehensive annotation remains a challenge....
Evidence for large inversion polymorphisms in the human genome from HapMap data (2006)
Bansal, Vikas, Bashir, Ali, Bafna, Vineet
Knowledge about structural variation in the human genome has grown tremendously in the past few years. However, inversions represent a class of structural variation that remains difficult to detect....
Zhang, Shaojie, Borovok, Ilya, Aharonowitz, Yair, Sharan, Roded, Bafna, Vineet
Motivation: Recent studies have uncovered an “RNA world”, in which non coding RNA (ncRNA) sequences play a central role in the regulation of gene expression. Computational studies on ncRNA have...
Consensus folding of unaligned RNA sequences revisited (2005)
Vineet Bafna, Haixu Tang, Shaojie Zhang
As one of the earliest problems in computational biology, RNA secondary structure prediction (sometimes referred to as “RNA folding”) problem has attracted attention again, thanks to the recent...
Bafna V: Searching Genomes for Noncoding RNA Using FastR (2005)
Shaojie Zhang, Brian Haas, Eleazar Eskin, Vineet Bafna
Abstract—The discovery of novel noncoding RNAs has been among the most exciting recent developments in biology. It has been hypothesized that there is, in fact, an abundance of functional noncoding...
Identification of post-translational modifications via blind search of mass-spectra (2005)
Post-translational modifications (PTMs) are of great biological importance. Most existing approaches perform a restrictive search that can only take into account a few types of PTMs and ignore all...
Orthologous repeats and mammalian phylogenetic inference. Genome Res (2005)
Ali Bashir, Chun Ye, Alkes L. Price, Vineet Bafna
Determining phylogenetic relationships between species is a difficult problem, and many phylogenetic relationships remain unresolved, even among eutherian mammals. Repetitive elements provide...
Improved recombination lower bounds for haplotype data (2005)
ABSTRACT Recombination is an important evolutionary mechanism responsible for the genetic diversity in humans and other organisms. Recently, there has been extensive research on understanding the...
Consensus folding of unaligned RNA sequences revisited (2005)
Vineet Bafna, Haixu Tang, Shaojie Zhang
Abstract. As one of the earliest problems in computational biology, RNA secondary structure prediction (sometimes referred to as “RNA folding”) problem has attracted attention again, thanking to...
Orthologous repeats and mammalian phylogenetic inference (2005)
Bashir, Ali, Ye, Chun, Price, Alkes L., Bafna, Vineet
Determining phylogenetic relationships between species is a difficult problem, and many phylogenetic relationships remain unresolved, even among eutherian mammals. Repetitive elements provide...
A note on efficient computation of haplotypes via perfect phylogeny (2004)
Vineet Bafna, Dan Gusfield, Sridhar Hannenhalli, Shibu Yooseph
With the completion of the draft sequencing of the human genome [13, 18], a natural next step is to identify, and characterize, the variations that explain the diversity of the human species. Much of...
A survey of computational methods for determining haplotypes (2004)
Bjarni V. Halldórsson, Vineet Bafna, Nathan Edwards, Shibu Yooseph, Sorin Istrail
Abstract. It is widely anticipated that the study of variation in the human genome will provide a means of predicting risk of a variety of complex diseases. Single nucleotide polymorphisms (SNPs) are...
A survey of computational methods for determining haplotypes (2004)
Bjarni V. Halldórsson, Vineet Bafna, Nathan Edwards, Shibu Yooseph, Sorin Istrail
Abstract. It is widely anticipated that the study of variation in the human genome will provide a means of predicting risk of a variety of complex diseases. Single nucleotide polymorphisms (SNPs) are...
Mass Spectrometry is the tool of choice for Proteomics, with applications to peptide sequencing, protein structure prediction, protein-protein interactions, and many others. Continued improvements in...
Mass Spectrometry is the tool of choice for Proteomics, with applications to peptide sequencing, protein structure prediction, protein-protein interactions, and many others. Continued improvements in...
Optimal Haplotype Block-Free Selection of Tagging SNPs for Genome-Wide Association Studies (2004)
Halldórsson, Bjarni V., Bafna, Vineet, Lippert, Ross, Schwartz, Russell, De La Vega, Francisco M., Clark, Andrew G., ...
It is widely hoped that the study of sequence variation in the human genome will provide a means of elucidating the genetic component of complex diseases and variable drug responses. A major...
Combinatorial problems arising in SNP and Haplotype Analysis (2003)
Bjarni V. Halldórsson, Vineet Bafna, Nathan Edwards, Shibu Yooseph, Sorin Istrail
Abstract. It is widely anticipated that the study of variation in the human genome will provide a means of predicting riskof a variety of complex diseases. This paper presents a number of algorithmic...
Haplotypes and informative SNP selection algorithms: don’t block out information (2003)
Vineet Bafna, Bjarni V. Halldórsson, Russell Schwartz, Andrew G. Clark
It is widely hoped that variation in the human genome will provide a means of predicting risk of a variety of complex, chronic diseases. A major stumbling block to the successful identification of...
Robustness of inference of haplotype block structure (2003)
Russell Schwartz, Bjarni V. Halldórsson, Vineet Bafna, Andrew G. Clark, Sorin Istrail
In this report, we examine the validity of the haplotype block concept by comparing block decompositions derived from public data sets by variants of several leading methods of block detection. We...
Haplotyping as Perfect Phylogeny: A direct approach (2002)
Vineet Bafna, Vineet Bafna, Giuseppe Lancia, Dan Gusfield, Dan Gusfield, Shibu Yooseph, ...
A full Haplotype Map of the human genome will prove extremely valuable as it will be used in large-scale screens of populations to associate specific haplotypes with specific complex...
Haplotyping as perfect phylogeny: A direct approach (2002)
Vineet Bafna, Dan Gusfield, Shibu Yooseph
A full Haplotype Map of the human genome will prove extremely valuable as it will be used in large-scale screens of populations to associate specific haplotypes with specific complex...
Vineet Bafna, Dan Gus Eld, Shibu Yooseph, Vineet Bafna, Dan Gus, Shibu Yooseph X
A full HaplotypeMapof the human genome will prove extremely valuable as it will be used in large-scale screens of populations to associate speci c haplotypes with speci c complex geneticin uenced...
SCOPE: a probabilistic model for scoring tandem mass spectra against a peptide database (2001)
Proteomics, or the direct analysis of the expressed protein components of a cell, is critical to our understanding of cellular biological processes in normal and diseased tissue. A key requirement...
SCOPE: a probabilistic model for scoring tandem mass spectra against a peptide database (2001)
mass spectra against a peptide database
SCOPE: a probabilistic model for scoring tandem mass spectra against a peptide database (2001)
Bafna, Vineet, Edwards, Nathan
Proteomics, or the direct analysis of the expressed protein components of a cell, is critical to our understanding of cellular biological processes in normal and diseased tissue. A key requirement...
C.Y.: A polynomial-time approximation scheme for minimum routing cost spanning trees (1999)
Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-mao Chao, R. Ravi, ...
Abstract. Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair...
A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees (1998)
Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang
Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the...
A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees (1998)
Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang
Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1997)
Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup
We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = min T fk T \Gamma D...
Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles) (1996)
Vineet Bafna, Babu Narayanan, R. Ravi
We consider the following problem motivated by an application in computational molecular biology. We are given a set of weighted axis-parallel rectangles such that for any pair of rectangles and...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1996)
Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup
. We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = minT fk T \Gamma D...
Constant Ratio Approximations of Feedback Vertex Sets in Weighted Undirected Graphs (1996)
Vineet Bafna, P. Bergman, T. Fujito, Piotr Berman, Toshihiro Fujito
A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. We show that a feedback vertex set approximating a minimum one within a...
Vineet Bafna, Pave A. Pevzner*j
Sequence comparison in computational molecular biology is a powerful tool for deriving evolutionary and functional relationships between genes. However, classical alignment algorithms handle only...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1995)
Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup
We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric, that is, " = min T fk T; D k1 g. First we present...
Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles) (1995)
Vineet Bafna, Babu Narayanan, R. Ravi
We consider the following problem motivated by an application in computational molecular biology. We are given a set of weighted axis-parallel rectangles such that for any pair of rectangles and...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1995)
Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup
We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric, that is, " = min T fk T; D k1 g. First we present...
Not All Insertion Methods Yield Constant Approximate Tours in the Euclidean Plane (1994)
Vineet Bafna, Bala Kalyanasundaram, Kirk Pruhs
An insertion heuristic for the traveling salesman problem adds cities iteratively to an existing tour by replacing one edge with a two-edge path through the new city in the cheapest possible way....
Optimal Haplotype Block-Free Selection of Tagging SNPs for Genome-Wide Association Studies
Halldórsson, Bjarni V., Bafna, Vineet, Lippert, Ross, Schwartz, Russell, De La Vega, Francisco M., Clark, Andrew G., ...
It is widely hoped that the study of sequence variation in the human genome will provide a means of elucidating the genetic component of complex diseases and variable drug responses. A major...
Orthologous repeats and mammalian phylogenetic inference
Bashir, Ali, Ye, Chun, Price, Alkes L., Bafna, Vineet
Determining phylogenetic relationships between species is a difficult problem, and many phylogenetic relationships remain unresolved, even among eutherian mammals. Repetitive elements provide...
Optimal Haplotype Block-Free Selection of Tagging SNPs for Genome-Wide Association Studies
Halldórsson, Bjarni V., Bafna, Vineet, Lippert, Ross, Schwartz, Russell, De La Vega, Francisco M., Clark, Andrew G., ...
It is widely hoped that the study of sequence variation in the human genome will provide a means of elucidating the genetic component of complex diseases and variable drug responses. A major...
Orthologous repeats and mammalian phylogenetic inference
Bashir, Ali, Ye, Chun, Price, Alkes L., Bafna, Vineet
Determining phylogenetic relationships between species is a difficult problem, and many phylogenetic relationships remain unresolved, even among eutherian mammals. Repetitive elements provide...
The Sorcerer II Global Ocean Sampling Expedition: Expanding the Universe of Protein Families
Yooseph, Shibu, Sutton, Granger, Rusch, Douglas B, Halpern, Aaron L, Williamson, Shannon J, Remington, Karin, ...
Metagenomics projects based on shotgun sequencing of populations of micro-organisms yield insight into protein families. We used sequence similarity clustering to explore proteins with a...
Evidence for large inversion polymorphisms in the human genome from HapMap data
Bansal, Vikas, Bashir, Ali, Bafna, Vineet
Knowledge about structural variation in the human genome has grown tremendously in the past few years. However, inversions represent a class of structural variation that remains difficult to detect....
Improving gene annotation using peptide mass spectrometry
Tanner, Stephen, Shen, Zhouxin, Ng, Julio, Florea, Liliana, Guigó, Roderic, Briggs, Steven P., ...
Annotation of protein-coding genes is a key goal of genome sequencing projects. In spite of tremendous recent advances in computational gene finding, comprehensive annotation remains a challenge....
The Diploid Genome Sequence of an Individual Human
Levy, Samuel, Sutton, Granger, Ng, Pauline C, Feuk, Lars, Halpern, Aaron L, Walenz, Brian P, ...
Presented here is a genome sequence of an individual human. It was produced from ∼32 million random DNA fragments, sequenced by Sanger dideoxy technology and assembled into 4,528 scaffolds,...
Gupta, Nitin, Tanner, Stephen, Jaitly, Navdeep, Adkins, Joshua N., Lipton, Mary, Edwards, Robert, ...
While bacterial genome annotations have significantly improved in recent years, techniques for bacterial proteome annotation (including post-translational chemical modifications, signal peptides,...
Evaluation of Paired-End Sequencing Strategies for Detection of Genome Rearrangements in Cancer
Bashir, Ali, Volik, Stanislav, Collins, Colin, Bafna, Vineet, Raphael, Benjamin J.
Paired-end sequencing is emerging as a key technique for assessing genome rearrangements and structural variation on a genome-wide scale. This technique is particularly useful for detecting...
Gupta, Nitin, Benhamida, Jamal, Bhargava, Vipul, Goodman, Daniel, Kain, Elisabeth, Kerman, Ian, ...
Recent proliferation of low-cost DNA sequencing techniques will soon lead to an explosive growth in the number of sequenced genomes and will turn manual annotations into a luxury. Mass spectrometry...
An MCMC algorithm for haplotype assembly from whole-genome sequence data
Bansal, Vikas, Halpern, Aaron L., Axelrod, Nelson, Bafna, Vineet
In comparison to genotypes, knowledge about haplotypes (the combination of alleles present on a single chromosome) is much more useful for whole-genome association studies and for making inferences...
Discovery and revision of Arabidopsis genes by proteogenomics
Castellana, Natalie E., Payne, Samuel H., Shen, Zhouxin, Stanke, Mario, Bafna, Vineet, Briggs, Steven P.
Gene annotation underpins genome science. Most often protein coding sequence is inferred from the genome based on transcript evidence and computational predictions. While generally correct, gene...
A Multidimensional Chromatography Technology for In-depth Phosphoproteome Analysis*S⃞
Albuquerque, Claudio P., Smolka, Marcus B., Payne, Samuel H., Bafna, Vineet, Eng, Jimmy, Zhou, Huilin
Protein phosphorylation is a post-translational modification widely used to regulate cellular responses. Recent studies showed that global phosphorylation analysis could be used to study signaling...
McKernan, Kevin Judd, Peckham, Heather E., Costa, Gina L., McLaughlin, Stephen F., Fu, Yutao, Tsung, Eric F., ...
We describe the genome sequencing of an anonymous individual of African origin using a novel ligation-based sequencing assay that enables a unique form of error correction that improves the raw...