Spectrum alignment: efficient resequencing by hybridization.
Recent high-density microarray technologies allow, in principle, the determination of all k-mers that appear along a DNA sequence, for k = 8 - 10 in a single experiment on a standard chip. The k-mer contents, also called the spectrum of the sequence, is not sufficient to uniquely reconstruct a sequence longer than a few hundred bases. We have devised a polynomial algorithm that reconstructs the sequence, given the spectrum and a homologous sequence. This situation occurs, for example, in the identification of single nucleotide polymorphisms (SNPs), and whenever a homologue of the target sequence is known. The algorithm is robust, can handle errors in the spectrum and assumes no knowledge of the k-mer multiplicities. Our simulations show that with realistic levels of SNPs, the algorithm correctly reconstructs a target sequence of length up to 2,000 nucleotides when a polymorphic sequence is known. The technique is generalized to handle profiles and HMMs as input instead of a single homologous sequence.
Pe'er
I
I
Department of Computer Science, Tel Aviv University, Israel. izik@math.tau.ac.il
Shamir
R
R
D000465:Algorithms; D000818:Animals; D016678:Genome; D006801:Humans; D008390:Markov Chains; D009693:Nucleic Acid Hybridization; D020411:Oligonucleotide Array Sequence Analysis; D016415:Sequence Alignment / Q000379:methods*