We introduce binomial edge ideals attached to a simple graph $G$ and study their algebraic properties. We characterize those graphs for which the quadratic generators form a Grobner basis in a lexicographic order induced by a vertex labeling. Such gr
aphs are chordal and claw-free. We give a reduced squarefree Grobner basis for general $G$. It follows that all binomial edge ideals are radical ideals. Their minimal primes can be characterized by particular subsets of the vertices of $G$. We provide sufficient conditions for Cohen--Macaulayness for closed and nonclosed graphs. Binomial edge ideals arise naturally in the study of conditional independence ideals. Our results apply for the class of conditional independence ideals where a fixed binary variable is independent of a collection of other variables, given the remaining ones. In this case the primary decomposition has a natural statistical interpretation
