The well known family of binary twin-prime sequences is generalised to the multiple-valued case by employing a polyphase representation of the sequence elements. These polyphase versions exhibit similar periodic and aperiodic auto-correlation properties to their binary counterparts, and are referred to as q-phase related-prime (RP) sequences. These sequences have length L=r·s, for r and s both prime, and with s=r+k. They are constructed by combining two polyphase Legendre sequences of lengths r and s, and modifying the resulting composite sequence at certain points. A two-dimensional array structure is employed in the construction and analysis of these sequences. The original q-phase Legendre sequences are derived by converting the index sequences of lengths r and s to modulo-q form. When q is even, two classes of RP sequence arise, depending on whether L≡q+1 mod 2q or L≡1 mod 2q. For odd q, only a single class is available, and here L≡1 mod 2q. The out-of-phase periodic correlation values of these RP sequences are independent of the sequence length, and depend only on the number of phases q and the difference k between the two related primes. The maximum out-of-phase correlation values is given by 1−k. Tables of available sequences are presented.