Many large protein-nucleic acid complexes exhibit allosteric regulation. In these systems, the propagation of the allosteric signaling is strongly coupled to conformational dynamics and catalytic function, challenging state-of-the-art analytical methods. Here, we review established and innovative approaches used to elucidate allosteric mechanisms in these complexes. Specifically, we report network models derived from graph theory and centrality analyses in combination with molecular dynamics (MD) simulations, introducing novel schemes that implement the synergistic use of graph theory with enhanced simulations methods and ab-initio MD. Accelerated MD simulations are used to construct "enhanced network models", describing the allosteric response over long timescales and capturing the relation between allostery and conformational changes. "Ab-initio network models" combine graph theory with ab-initio MD and quantum mechanics/molecular mechanics (QM/MM) simulations to describe the allosteric regulation of catalysis by following the step-by-step dynamics of biochemical reactions. This approach characterizes how the allosteric regulation changes from reactants to products and how it affects the transition state, revealing a tense-to-relaxed allosteric regulation along the chemical step. Allosteric models and applications are showcased for three paradigmatic examples of allostery in protein-nucleic acid complexes: (i) the nucleosome core particle, (ii) the CRISPR-Cas9 genome editing system and (iii) the spliceosome. These methods and applications create innovative protocols to determine allosteric mechanisms in protein-nucleic acid complexes that show tremendous promise for medicine and bioengineering.