Backported dependency gets lower version number than the required one

Originally posted at http://askubuntu.com/questions/895965/how-to-properly-backport-dependencies-when-backporting-a-package-to-ppa

I want to backport package X that depends on Y, so both packages need backporting. First, I backport Y, so it becomes something like Y-a.b~ubuntu123. When I now try to backport X it complains about missing dependency Y-a.b due to weird version comparison algorithm, which makes effectively Y-a.b~ubuntu123 < Y-a.b :

(From debian.org):
First the initial part of each string consisting entirely of non-digit characters is determined. These two parts (one of which may be empty) are compared lexically. If a difference is found it is returned. The lexical comparison is a comparison of ASCII values modified so that all the letters sort earlier than all the non-letters and so that a tilde sorts before anything, even the end of a part. For example, the following parts are in sorted order from earliest to latest: ~~, ~~a, ~, the empty part, a.