Methods and compositions for constructing and producing recombinant adenovirus-based vector vaccines are provided. In particular aspects, there are be provided compositions and methods involving adenovirus vectors comprising genes for target antigens, such as novel antigens of HPV E6 and/or HPV E7 for use in treatment methods that generate highly reactive anti-HPV and anti-tumor immune responses in subjects with preexisting immunity to adenovirus.