Reactive nitrogen oxide species (RNOS) are produced by the human immune system in response to bacterial infection and thus the bacterial response to RNOS is relevant to the understanding of pathogenesis. To identify RNOS transcriptional response regulators and the underlying network structure in E. coli, we have used Network Component Analysis (NCA) to decompose transcriptome measurements into transcription factor activity (TFA) and partial network structure. We have employed an iterative investigation between NCA and transcriptomic experiments in order to include non-traditional transcriptional response elements, such as the stringent response, in the data analysis. In this manner, we have identified the ArcAB two-component system, iron-sulfur cluster repair regulator IscR, known RNOS-response regulator NorR, and the stringent response as RNOS response elements in E. coli. Additionally, we have identified new potential regulatory connections within the response network.