# Determining if a genetic sequence is palindromic

Adding another level to my previous question on 'normal' palindrome identification, in this one I'm interested in identifying genetic palindromes. Here's my attempt:

#include <iterator>
#include <algorithm>
#include <array>

namespace detail
{
static constexpr std::array<char, 128> complement_table
{
4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
4, 84, 4, 71, 4,  4,  4, 67, 4, 4, 4, 4,  4, 4, 78, 4,
4, 4,  4, 4,  65, 65, 4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
4, 84, 4, 71, 4,  4,  4, 67, 4, 4, 4, 4,  4, 4, 4,  4,
4, 4,  4, 4,  65, 65, 4, 4,  4, 4, 4, 4,  4, 4, 4,  4
};
} // namespace detail

inline constexpr char complement(const char base)
{
return detail::complement_table[base];
}

namespace detail
{
template <typename RandomIt>
bool is_palindromic(RandomIt first, RandomIt last, std::random_access_iterator_tag)
{
if (first == last) return true;

const auto size = std::distance(first, last);

if (size % 2 != 0) return false;

return std::equal(first, std::next(first, size / 2), std::make_reverse_iterator(last),
[] (const char lhs, const char rhs) {
return lhs == complement(rhs);
});
}

template <typename BidirIt>
bool is_palindromic(BidirIt first, BidirIt last, std::bidirectional_iterator_tag)
{
if (first == last)   return true;
if (first == --last) return false;

for (; first != last; ++first, --last) {
if (*first != complement(*last)) return false;
if (std::next(first) == last) return true;
}

return false;
}
} // namespace detail

template <typename BidirIt>
bool is_palindromic(BidirIt first, BidirIt last)
{
return detail::is_palindromic(first, last, typename std::iterator_traits<BidirIt>::iterator_category {});
}

template <typename SequenceType>
bool is_palindromic(const SequenceType& sequence)
{
return is_palindromic(std::cbegin(sequence), std::cend(sequence));
}


Used as such:

#include <iostream>
#include <string>
#include <list>

int main()
{
std::cout << std::boolalpha;
std::string str {"ACCTAGGT"};
std::cout << is_palindromic(str) << std::endl;
std::list<char> lst {str.cbegin(), str.cend()};
std::cout << is_palindromic(lst) << std::endl;
return 0;
}


Performance is my primary concern here. Comments and suggested improvements are welcome!

• I see that "N" is its own complement, but there's no compliment for "n". Is that intentional? Commented Jan 28, 2016 at 5:28
• In fact, will your table work if the string is of mixed or all lower case? For example, "A" has a compliment of "T" and vice-versa, but "a" has a complement of "T" and "t" a compliment of "A". It seems like if the string is all lowercase, it won't work properly. Commented Jan 28, 2016 at 5:38
• @user1118321 Fair point, I'm also missing other amino acid codes (H, D, B, etc). I'm not really sure if there's an accepted way of dealing with lower case / mixed codes. In my experience, lower case codes are rarely used, and usually a marker of some sort (e.g. areas of low complexity). Commented Jan 28, 2016 at 8:03
• This definitely doesn't work on non-ASCII systems, though I guess you probably don't care about them.
– T.C.
Commented Feb 1, 2016 at 4:40
• Re the above comments: The proper primitive here isn't char complement(char); it's bool are_complementary(char, char). If you rewrite the code that way, I'll do a style review. ;) Commented Feb 1, 2016 at 9:24