
Flatulence (gassy dog) is something I'm really hot about, living with a breed prone to GDV (and despite my best efforts, having had 4 cases, 2 'fatal' over the years). I avoid cereal-based food as much as I can, and especially feed containing soya. I test - drop a piece of kibble in warm water to see how much it expands too. I have seen no relationship between protein and gas much as other than with puppies (and even then I keep a puppy food at no higher than 26% max), I tend to look for a food that's no higher than 22% protein. Apart from the last case, years ago now (fingers x-d) where he was 8, fit and healthy and still on good exercise, the other 3 were elderly males.
Most dog food contains probiotics these days, but you could try adding a bit of natural yogurt and see if this helps.