/* BaitFisher (version 1.2.8) a program for designing DNA target enrichment baits
* BaitFilter (version 1.0.6) a program for selecting optimal bait regions
* Copyright 2013-2017 by Christoph Mayer
*
* This source file is part of the BaitFisher-package.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with BaitFisher. If not, see .
*
*
* For any enquiries send an Email to Christoph Mayer
* c.mayer.zfmk@uni-bonn.de
*
* When publishing work that is based on the results please cite:
* Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
*
*/
#ifndef DNA_ROUTINES_H
#define DNA_ROUTINES_H
/* Todo: count DNA bases, guess data type, is AA, etc. */
// Changes 10/11.11.2016:
// * Removed a bug: (c == 'O' && c == 'U') should read (c == 'O' || c == 'U').
// The impact of this error is low. Basically, we overlook O or U as not allowed amino acids.
// Since they should not occur in normal amino acid sequences, it does not make much of a difference.
// * added the blosum symbols, lists and functions
// * added some upper lists and functions.
// * added a look-up table for the blosum symbols. This is much more efficient.
// * removed z from aa_symbols, aa_symbols_ext and _upper, since it as an ambiguity character.
#include
#include
static const char DNARNA_symbols[] = "aAcCgGtTuU";
static const char DNARNA_symbols_upper[] = "ACGTU";
static const char aa_symbols[] = "aArRnNdDcCeEqQgGhHiIlLkKmMfFpPsStTwWyYvVxX";
static const char aa_symbols_upper[] = "ARNDCEQGHILKMFPSTWYVX";
// Extended also includes: O and U:
static const char aa_symbols_ext[] = "aArRnNdDcCeEqQgGhHiIlLkKmMfFpPsStTwWyYvVxXuUoO*";
static const char aa_symbols_ext_upper [] = "ARNDCEQGHILKMFPSTWYVXUO*";
static const char non_aa_in_ABC [] = "BJOUZbjouz";
// AA ambiguity characters: J is a very rare ambiguity character also included in this set.
// J is not allowed in many programs.
static const char aa_ambig [] = "bBzZjJxX";
// Usually a safe list of allowed characters are those in the blosum matrix:
// Lists the symbols that are allowed in the blosum matrix: Contains B,Z but not J as ambiguity character.
// See also the look up tables: is_aa_blosum_code[] and is_aa_blosum_code_or_gap[]
static const char aa_symbols_blosum[] = "aArRnNdDcCeEqQzZgGhHiIlLkKmMfFpPsStTwWyYvVbBxX*";
static const char aa_symbols_blosum_upper [] = "ARNDCEQZGHILKMFPSTWYVBX*";
static const char non_aa_symbols_blosum[] = "jJoOuU";
static const char non_aa_symbols_blosum_upper [] = "JOU";
static const char DNARNA_iupac_symbols [] = "aAcCgGtTuURYSWryswKMBDkmbdHVNhvn";
static const char phylip_DNARNA_allowed_symbols [] = "?-nNaAcCgGtTuURYSWryswKMBDkmbdHVhvoOxX";
static const char phylip_neither_aa_dna_symbol [] = "jJzZ";
static const char allowed_non_ABC [] = "-?*";
// O and U are special amino acids that are usually not in the models.
// Chars that are not an aa symbol: B, J, O, U, Z
// X is the amibuity code
// Includes the symbols which occur in the blosum matrices:
const int is_aa_blosum_code_lookup[] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,1,0,0,0,0,0,0,0, // 40-49 45: - is not included, 42: * included
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,0,0,1,1,1,1,1, // 60-69 63: ? is not included
1,1,1,1,0,1,1,1,1,0, // 70-79
1,1,1,1,1,0,1,1,1,1, // 80-89
1,0,0,0,0,0,0,1,1,1, // 90-99
1,1,1,1,1,1,0,1,1,1, //100-109
1,0,1,1,1,1,1,0,1,1, //110-119
1,1,1,0,0,0,0,0 //120-127
};
// Includes the symbols which occur in the blosum matrices and the gap character:
const int is_aa_blosum_code_or_gap_lookup[] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,1,0,0,1,0,0,0,0, // 40-49 45: - is included, 42: * included
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,0,0,1,1,1,1,1, // 60-69 63: ? is not included
1,1,1,1,0,1,1,1,1,0, // 70-79
1,1,1,1,1,0,1,1,1,1, // 80-89
1,0,0,0,0,0,0,1,1,1, // 90-99
1,1,1,1,1,1,0,1,1,1, //100-109
1,0,1,1,1,1,1,0,1,1, //110-119
1,1,1,0,0,0,0,0 //120-127
};
// Inlcudes all DNA symbols, no ambiguity characters
const char is_DNA_lookup[128] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,0,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,0,0,1,0,1,0,0, // 60-69 63:'?', 65:'A' to 69:'E'
0,1,0,0,0,0,0,0,0,0, // 70-79
0,0,0,0,1,0,0,0,0,0, // 80-89
0,0,0,0,0,0,0,1,0,1, // 90-99
0,0,0,1,0,0,0,0,0,0, //100-109
0,0,0,0,0,0,1,0,0,0, //110-119
0,0,0,0,0,0,0,0 //120-127
};
// Inlcudes all DNA symbols and gap '-', no ambiguity characters
const char is_DNA_or_GAP_lookup[128] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,1,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,0,0,1,0,1,0,0, // 60-69 63:'?', 65:'A' to 69:'E'
0,1,0,0,0,0,0,0,0,0, // 70-79
0,0,0,0,1,0,0,0,0,0, // 80-89
0,0,0,0,0,0,0,1,0,1, // 90-99
0,0,0,1,0,0,0,0,0,0, //100-109
0,0,0,0,0,0,1,0,0,0, //110-119
0,0,0,0,0,0,0,0 //120-127
};
// Inlcudes all ambiguity characters as well as ?
const char is_DNA_or_AMBIG_lookup[128] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,0,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,1,0,1,1,1,1,0, // 60-69 63:'?', 65:'A' to 69:'E'
0,1,1,0,0,1,0,1,1,0, // 70-79
0,0,1,1,1,0,1,1,0,1, // 80-89
0,0,0,0,0,0,0,1,1,1, // 90-99
1,0,0,1,1,0,0,0,0,0, //100-109
0,0,0,0,1,0,1,0,1,1, //110-119
0,1,0,0,0,0,0,0 //120-127
};
// Inlcudes all ambiguity characters as well as ? and -
const char is_DNA_or_AMBIG_or_GAP_lookup[128] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,1,0,0,0,0, // 40-49 45: - is included
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,1,0,1,1,1,1,0, // 60-69 63:'?', 65:'A' to 69:'E'
0,1,1,0,0,1,0,1,1,0, // 70-79
0,0,1,1,1,0,1,1,0,1, // 80-89
0,0,0,0,0,0,0,1,1,1, // 90-99
1,0,0,1,1,0,0,0,0,0, //100-109
0,0,0,0,1,0,1,0,1,1, //110-119
0,1,0,0,0,0,0,0 //120-127
};
/* inline bool is_DNA_base_upper(char c) */
/* { */
/* if (c == 'A' || c == 'C' || c == 'G' || c == 'T' ) */
/* return true; */
/* return false; */
/* } */
/* inline bool is_DNA_base_lower(char c) */
/* { */
/* if (c == 'a' || c == 'c' || c == 'g' || c == 't' ) */
/* return true; */
/* return false; */
/* } */
// Only defined if c <= 127
inline bool is_DNA_base(char c)
{
return is_DNA_lookup[(int)c];
}
inline bool is_DNA_base_or_GAP(char c)
{
return is_DNA_or_GAP_lookup[(int)c];
}
inline bool is_DNA_or_DNA_ambig(char c)
{
return is_DNA_or_AMBIG_lookup[(int)c];
}
inline bool is_DNA_or_DNA_ambig_or_GAP(char c)
{
return is_DNA_or_AMBIG_or_GAP_lookup[(int)c];
}
inline bool is_DNA_or_RNA_base(char c)
{
if (c == 'A' || c == 'C' || c == 'G' || c == 'T' ||
c == 'a' || c == 'c' || c == 'g' || c == 't' || c == 'U' || c == 'u')
return true;
return false;
}
inline bool is_allowed_non_ABC(char c)
{
if (c == '-' || c == '?' || c == '*')
return true;
else
return false;
}
inline bool is_phylip_aa_dna_symbol(char c) // Does not include -? or similar
{
// Only one character is not allowed:
if (c=='o' || c == 'O')
return false;
if (c >='a' && c <= 'z')
{
return true;
}
else if (c >='A' && c <= 'Z')
{
return true;
}
return false;
}
inline bool is_gap(char c)
{
return c == '-';
}
// Only defined if c <= 127
// Includes only DNA ambig symbols. Does not include DNA symbols. See also is_DNA_or_AMBIG below.
inline bool is_DNA_ambig(char c)
{
return is_DNA_or_AMBIG_lookup[(int)c] && !is_DNA_lookup[(int)c];
/* if (c == 'N' || c == '?' || c == 'n' || */
/* c == 'R' || c == 'Y' || c == 'S' || c == 'W' || */
/* c == 'r' || c == 'y' || c == 's' || c == 'w' || */
/* c == 'K' || c == 'M' || c == 'B' || c == 'D' || */
/* c == 'k' || c == 'm' || c == 'b' || c == 'd' || */
/* c == 'H' || c == 'V' || */
/* c == 'h' || c == 'v') */
/* return true; */
/* else */
/* return false; */
}
/* inline bool is_DNA_iupac_ambig_upper(char c) */
/* { */
/* if (c == 'N' || c == '?' || */
/* c == 'R' || c == 'Y' || c == 'S' || c == 'W' || */
/* c == 'K' || c == 'M' || c == 'B' || c == 'D' || */
/* c == 'H' || c == 'V') */
/* return true; */
/* else */
/* return false; */
/* } */
// A list can be found here: https://en.wikipedia.org/wiki/Amino_acid
// The acceptance of J as an ambiguous amino acid symbol is low.
// J does not occur in the blosm matrix and is not allowed in some programs.
inline bool is_aa_ambig(char c)
{
if (c == 'b' || c == 'B' || c == '?' || c == 'x' || c == 'X' ||
c == 'j' || c == 'J' || c == 'z' || c == 'Z')
return true;
else
return false;
}
inline bool is_aa_blosum_code(unsigned char c)
{
return (is_aa_blosum_code_lookup[c] != 0);
}
inline bool is_aa_blosum_code_or_gap(unsigned char c)
{
return (is_aa_blosum_code_or_gap_lookup[c] != 0);
}
inline int is_aa_upper(char c)
{
if (c >='A' && c <= 'Z')
{
// AA ambigs:
if (c == 'B' || c == 'X' || c == 'J' || c == 'Z')
return false;
// The few symbols that represent nothing.
// Indeed they are listed as the 21st and 22nd amino acid in https://en.wikipedia.org/wiki/Amino_acid
// But they are usually not handled by programs, so we return false.
if (c == 'O' || c == 'U') // OU
return false;
return true;
}
return false;
}
inline int is_aa_or_aa_ambig(char c) // includes '?' and B, Z, J, X
{
if (c >='a' && c <= 'z')
{
if (c != 'o' && c != 'u') // Only not allowed characters in a..z are: ou
return true;
}
else if (c >='A' && c <= 'Z')
{
if (c != 'O' && c != 'U') // Only not allowed characters in a..z are: OU
return true;
}
if (c == '?' || c == '*')
return true;
return false;
// return (strchr(aa_symbols, c) != NULL);
}
inline int is_aa_or_aa_ambig_extended(char c) // O and U are allowed // includes '?' and B, Z, J, X
{
if (c >='a' && c <= 'z')
{
return true;
}
else if (c >='A' && c <= 'Z')
{
return true;
}
if (c == '?' || c == '*')
return true;
return false;
// return (strchr(aa_symbols, c) != NULL);
}
inline char complementBase_of_upper(char c)
{
switch (c) {
case 'A': c = 'T'; break;
case 'T': c = 'A'; break;
case 'G': c = 'C'; break;
case 'C': c = 'G'; break;
case 'R': c = 'Y'; break;
case 'Y': c = 'R'; break;
case 'M': c = 'K'; break;
case 'K': c = 'M'; break;
case 'B': c = 'V'; break;
case 'V': c = 'B'; break;
case 'D': c = 'H'; break;
case 'H': c = 'D'; break;
case 'N': c = 'N'; break;
case '?': c = '?'; break;
case '-': c = '-'; break;
default:
c = '*';
break;
}
return c;
}
inline char complementBase_of_lower(char c)
{
switch (c) {
case 'a': c = 't'; break;
case 't': c = 'a'; break;
case 'g': c = 'c'; break;
case 'c': c = 'g'; break;
case 'r': c = 'y'; break;
case 'y': c = 'r'; break;
case 'm': c = 'k'; break;
case 'k': c = 'm'; break;
case 'b': c = 'v'; break;
case 'v': c = 'b'; break;
case 'd': c = 'h'; break;
case 'h': c = 'd'; break;
case 'n': c = 'n'; break;
case '?': c = '?'; break;
case '-': c = '-'; break;
default:
c = '*';
break;
}
return c;
}
inline char complementBase(char c)
{
if ( isupper(c) )
return complementBase_of_upper(c);
else
return complementBase_of_lower(c);
}
inline void CG_AT_content_in_region(const char *beg, const char *end, unsigned &AT, unsigned &CG)
{
AT = 0;
CG = 0;
char c;
while (beg != end)
{
c = *beg;
if (c == 'C' || c == 'c' || c == 'G' || c == 'g')
++CG;
else if (c == 'A' || c == 'a' || c == 'T' || c == 't')
++AT;
++beg;
}
}
inline void content_in_region_DNA(const char *beg, const char *end, unsigned &AT, unsigned &CG, unsigned &gap, unsigned &ambig, unsigned &unknown)
{
AT = 0;
CG = 0;
gap = 0;
ambig = 0;
unknown = 0;
char c;
while (beg != end)
{
c = *beg;
if (c == 'C' || c == 'c' || c == 'G' || c == 'g')
++CG;
else if (c == 'A' || c == 'a' || c == 'T' || c == 't')
++AT;
else if (c == '-')
++gap;
else if (is_DNA_ambig(c) )
++ambig;
else
++unknown;
++beg;
}
}
inline bool is_aa_blosum_code_or_gap_sequence(const char *p1, const char *p2, unsigned *offending_pos)
{
const char *startp = p1;
while (p1 != p2)
{
if (!is_aa_blosum_code_or_gap(*p1) )
{
*offending_pos = p1 - startp;
return false;
}
++p1;
}
return true;
}
// Recoding symbols:
// A char can hold 8 bits, enough for 8 characters to be "in or out",
// to be switched on or off. Thus a char can be used to hold
// all bases including ambiguities as follows:
// Say A, C, G, T are the bits 1,2,3,4,
// the ambiguity {A,C} is 1+2 = 3
// A: 65, 97 -> 1
// C: 67, 99 -> 2
// G: 71,103 -> 4
// T: 84,116 -> 8
// R(AG): 82,114 -> 5
// Y(CT): 89,121 -> 10
// S(CG): 83,115 -> 6
// W(TA): 87,119 -> 9
// K(TG): 75,107 -> 12
// M(CA): 77,109 -> 3
// B(CTG): 66,98 -> 14
// D(ATG): 68,100 -> 13
// H(ATC): 72,104 -> 11
// V(ACG): 86,118 -> 7
// N(ACGT): 78,110 -> 15
// - 45 -> 0
// ? 63 -> 15
const char ascii2recode_DNA[128] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,0,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,15,0,1,14,2,13,0, // 60-69
0,4,11,0,0,12,0,3,15,0, // 70-79
0,0,5,6,8,0,7,9,0,10, // 80-89
0,0,0,0,0,0,0,1,14,2, // 90-99
13,0,0,4,11,0,0,0,0,0, //100-109
0,0,0,0,5,0,8,0,7,9, //110-119
0,10,0,0,0,0,0,0 //120-127
};
const char recode2ascii_DNA[128] = {
45,65,67,77,71,82,83,86,84,87, // 0- 9
89,72,75,68,66,78,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,0,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,0,0,0,0,0,0,0, // 60-69
0,0,0,0,0,0,0,0,0,0, // 70-79
0,0,0,0,0,0,0,0,0,0, // 80-89
0,0,0,0,0,0,0,0,0,0, // 90-99
0,0,0,0,0,0,0,0,0,0, //100-109
0,0,0,0,0,0,0,0,0,0, //110-119
0,0,0,0,0,0,0,0 //120-127
};
const char recodeISDNAamig[128] = {
0,0,0,1,0,1,1,1,0,1, // 0- 9
1,1,1,1,1,1,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,0,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,0,0,0,0,0,0,0, // 60-69
0,0,0,0,0,0,0,0,0,0, // 70-79
0,0,0,0,0,0,0,0,0,0, // 80-89
0,0,0,0,0,0,0,0,0,0, // 90-99
0,0,0,0,0,0,0,0,0,0, //100-109
0,0,0,0,0,0,0,0,0,0, //110-119
0,0,0,0,0,0,0,0 //120-127
};
inline unsigned char recode_DNA(unsigned char c)
{
return ascii2recode_DNA[c];
}
inline unsigned char backrecode_DNA(unsigned char c)
{
return recode2ascii_DNA[c];
}
inline unsigned char recode_is_DNA_ambig(unsigned char c)
{
return recodeISDNAamig[c];
}
inline bool is_base_in_recode(unsigned char recode, unsigned char base)
{
return recode & recode_DNA(base);
}
inline bool is_valid_recode_DNA(unsigned char c)
{
if (c > 15)
return false;
else
return true;
}
inline bool is_recode_gap(unsigned char c)
{
return (c == 0);
}
// A Ala Alanine 01 65
// R Arg Arginine 02 82
// N Asn Asparagine 03 78
// D Asp Aspartic acid 08 68
// C Cys Cysteine 16 67
// Q Gln Glutamine 32 81
// E Glu Glutamic acid 64 69
// G Gly Glycine 128 71
// H His Histidine 256 72
// I Ile Isoleucine 512 73
// L Leu Leucine 1024 76
// K Lys Lysine 2048 75
// M Met Methionine 4096 77
// F Phe Phenylalanine 8192 70
// P Pro Proline 16384 80
// S Ser Serine 32768 83
// T Thr Threonine 65536 84
// W Trp Tryptophan 131072 87
// Y Tyr Tyrosine 262144 89
// V Val Valine 524288 86
// - 45 -> 0
// ? 63 -> 1048575
// X 88 -> 1048575
const int ascii2recode_aa[128] = {
0,0,0,0,0,0,0,0,0,0, // 0- 9
0,0,0,0,0,0,0,0,0,0, // 10-19
0,0,0,0,0,0,0,0,0,0, // 20-29
0,0,0,0,0,0,0,0,0,0, // 30-39
0,0,0,0,0,64,0,0,0,0, // 40-49
0,0,0,0,0,0,0,0,0,0, // 50-59
0,0,0,15,0,1,14,2,13,0, // 60-69
0,4,11,0,0,12,0,3,15,0, // 70-79
0,0,5,6,8,0,7,9,0,10, // 80-89
0,0,0,0,0,0,0,1,14,2, // 90-99
13,0,0,4,11,0,0,0,0,0, //100-109
0,0,0,0,5,0,8,0,7,9, //110-119
0,10,0,0,0,0,0,0 //120-127
};
#endif