El APK es un archivo contenedor, realmente es un archivo .zip firmado. Dentro del apk esta la aplicación en si con todo lo que esta necesita. A parte de eso, según he entendido el deodexar el .apk lo que hace es optimizarlo en tamaño y a la vez permite tematizar las apps, de ahí que la gente quiera ROM's deodexadas.