To increase the yield of DNA sequence generated by the 454 technology from small amounts of starting DNA, we investigated the efficiency of each step in the 454 library preparation process. We find that the last step, when the single-stranded library is released by NaOH, is inefficient and highly variable. When this step is replaced with heat treatment, library amounts dramatically increase. Furthermore, when sequencing templates are first isolated by NaOH treatment and subsequently by heat treatment, the sequences of both strands of individual template DNA molecules can be determined. Using this approach, we confirm that C/G base pairs observed as T/A base pairs in Neanderthal DNA sequences are due to a modification of the cytosine rather than guanine residues.