Genome-scale metabolic networks which have been automatically derived through sequence comparison techniques are necessarily incomplete. We propose a strategy that incorporates genomic sequence data and metabolite profiles into modeling approaches to arrive at improved gene annotations and more complete genome-scale metabolic networks. The core of our strategy is an algorithm that computes minimal sets of reactions by which a draft network has to be extended in order to be consistent with experimental observations. A particular strength of our approach is that alternative possibilities are suggested and thus experimentally testable hypotheses are produced. We carefully evaluate our strategy on the well-studied metabolic network of Escherichia coli, demonstrating how the predictions can be improved by incorporating sequence data. Subsequently, we apply our method to the recently sequenced green alga Chlamydomonas reinhardtii. We suggest specific genes in the genome of Chlamydomonas which are the strongest candidates for coding the responsible enzymes.