It sounds like you are looking for the semi-NMF algorithm, which relaxes the positive restriction on the input matrix (and one of the output matrixes). Mike Jordan has a paper discussing this technique including a description of an algorithm to compute it. link
I have to ask if this is really what you want to do. Gene expression data is inherently non-negative, which is why NMF is popular for gene expression analysis. Your large negative values are probably the result of a log-transform which you could undo and then apply a regular NMF. Ask whoever generated the data if any transformations were applied and consider undoing it and then running regular NMF. This is probably easier then rolling your own implementation of an exotic NMF variant.
Edit: If it's just a few negative entries, you could also consider removing the genes with negative entries.