Small animal positron emission tomography (PET) imaging often requires high resolution (∼few hundred microns) to enable accurate quantitation in small structures such as animal brains. Recently, we have developed a prototype ultrahigh resolution depth-of-interaction (DOI) PET system that uses CdZnTe detectors with a detector pixel size of 350 μm and eight DOI layers with a 250 μm depth resolution. Due to the large number of line-of-response (LOR) combinations of DOIs, the system matrix for reconstruction is 64 times larger than that without DOI. While a high resolution virtual ring geometry can be employed to simplify the system matrix and create a sinogram, the LORs in such a sinogram tend to be sparse and irregular, leading to potential degradation of the reconstructed image quality. In this paper, we propose a novel high resolution sinogram rebinning method in which a uniform sub-sampling DOI strategy is employed. However, even with the high resolution rebinning strategy, the reconstructed image tends to be very noisy due to insufficient photon counts in many high resolution sinogram pixels. To reduce noise effects, we developed a penalized maximum likelihood reconstruction framework with the Poisson log-likelihood and a non-convex total variation penalty. Here, an ordered subsets separable quadratic surrogate and alternating direction method of multipliers are utilized to solve the optimization. To evaluate the performance of the proposed sub-sampling method and the penalized maximum likelihood reconstruction technique, we perform simulations and preliminary point source experiments. By comparing the reconstructed images and profiles based on sinograms without DOI, with rebinned DOI and with sub-sampled DOI, we demonstrate that the proposed method with sub-sampled DOIs can significantly improve the image quality with lower dose and yield a high resolution of <300 μm.