Ubuntu's "Yum Whatprovides": Apt-File
Ubuntu has a "yum whatprovides" equivalent, but it's somewhat hard to find.
yum whatprovides is a great tool to figure out which package you need to get a certain file. yum whatprovides */dig will let you know that you need the install the bind-utils package to get dig.
Ubuntu has the same functionality, but you’ll need to follow a few steps to get there. First, install apt-file
apt-get install apt-file
Then, update the file cache
apt-file update
After that, you can search the cache using regexp.