Archaeal histones and the eucaryal (eucaryotic) nucleosome core histones have almost identical histone folds. Here, we show that DNA molecules selectively incorporated by rHMfB (recombinant archaeal histone B from Methanothermus fervidus) into archaeal nucleosomes from a mixture of similar to 10(14) random sequence molecules contain sequence motifs shown previously to direct eucaryal nucleosome positioning. The dinucleotides GC, AA (=TT) and TA are repeated at similar to 10 bp intervals, with the GC harmonic displaced similar to5 bp from the AA and TA harmonics [(GCN(3),AA or TA)(n)]. AT and CG were not strongly selected, indicating that TA not equal AT and GC not equal CG in terms of facilitating archaeal nucleosome assembly. The selected molecules have affinities for rHMfB ranging from similar to9 to 18-fold higher than the level of affinity of the starting population, and direct the positioned assembly of archaeal nucleosomes. Fourier-transform analyses have revealed that AA dinucleotides are much enriched at similar to 10.1 bp intervals, the helical repeat of DNA wrapped around a nucleosome, in the genomes of Eucarya and the histone-containing Euryarchaeota, but not in the genomes of Bacterin and Crenarchaeota, procaryotes that do not have histones. Facilitating histone packaging of genomic DNA has apparently therefore imposed constraints on genome sequence evolution, and since archaeal histones have no structure in addition to the histone fold, these constraints must result predominantly from histone fold-DNA contacts. Based on the three-domain universal phylogeny, histones and histone-dependent genome sequence evolution most likely evolved after the bacterial-archaeal divergence but before the archaeal-eucaryal divergence, and were subsequently lost in the Crenarchaeota. However, with lateral gene transfer, the first histone fold could alternatively have evolved after the archaeal-eucaryal divergence, early in either the euryarchaeal or eucaryal lineages. (C) 2000 Academic Press.