Каков хороший способ реализации получения консенсусной последовательности в Java?

У меня есть следующая проблема:

  • У меня есть 2 последовательности последовательностей ДНК (состоящих из ACGT), которые отличаются в одном или двух местах.
  • Найти различия тривиально, поэтому давайте просто проигнорируем это
  • для каждого различия я хочу получить символ консенсуса (например, M для A или C), который представляет обе возможности

Я знаю, что мог бы просто создать огромный каскад if, но я думаю, что это не только уродливо и сложно поддерживать, но и медленно.

Какой быстрый и простой способ реализовать это? Может быть, какая-то таблица поиска или матрица для комбинаций? Любые примеры кода будут с благодарностью. Я бы использовал Biojava, но текущая версия, которую я уже использую, не предлагает эту функциональность (или я еще не нашел ее...).

Обновление: здесь, кажется, немного путаницы. Символ консенсуса - это один символ, который обозначает один символ в обеих последовательностях.

String1 и String2, например, "ACGT" и "ACCT" - они не совпадают в позиции 2. Ооо, я хочу, чтобы консенсусная строка была ACST, потому что S обозначает "либо C, либо G"

Я хочу сделать такой метод:

char getConsensus(char a, char b)

Обновление 2: некоторые из предложенных методов работают, если у меня есть только 2 последовательности. Мне может потребоваться выполнить несколько итераций этих "согласований", чтобы входной алфавит мог увеличиться с "ACGT" до "ACGTRYKMSWBDHVN", что сделало бы некоторые из предложенных подходов довольно громоздкими для написания и поддержки.

Источник

6 ответов

Решение

Возможное решение с использованием перечислений, вдохновленных pablochan, с небольшим вкладом от biostar.stackexchange.com:

enum lut {
     AA('A'), AC('M'), AG('R'), AT('W'), AR('R'), AY('H'), AK('D'), AM('M'), AS('V'), AW('W'), AB('N'), AD('D'), AH('H'), AV('V'), AN('N'),
     CA('M'), CC('C'), CG('S'), CT('Y'), CR('V'), CY('Y'), CK('B'), CM('M'), CS('S'), CW('H'), CB('B'), CD('N'), CH('H'), CV('V'), CN('N'),
     GA('R'), GC('S'), GG('G'), GT('K'), GR('R'), GY('B'), GK('K'), GM('V'), GS('S'), GW('D'), GB('B'), GD('D'), GH('N'), GV('V'), GN('N'),
     TA('W'), TC('Y'), TG('K'), TT('T'), TR('D'), TY('Y'), TK('K'), TM('H'), TS('B'), TW('W'), TB('B'), TD('D'), TH('H'), TV('N'), TN('N'),
     RA('R'), RC('V'), RG('R'), RT('D'), RR('R'), RY('N'), RK('D'), RM('V'), RS('V'), RW('D'), RB('N'), RD('D'), RH('N'), RV('V'), RN('N'),
     YA('H'), YC('Y'), YG('B'), YT('Y'), YR('N'), YY('Y'), YK('B'), YM('H'), YS('B'), YW('H'), YB('B'), YD('N'), YH('H'), YV('N'), YN('N'),
     KA('D'), KC('B'), KG('K'), KT('K'), KR('D'), KY('B'), KK('K'), KM('N'), KS('B'), KW('D'), KB('B'), KD('D'), KH('N'), KV('N'), KN('N'),
     MA('M'), MC('M'), MG('V'), MT('H'), MR('V'), MY('H'), MK('N'), MM('M'), MS('V'), MW('H'), MB('N'), MD('N'), MH('H'), MV('V'), MN('N'),
     SA('V'), SC('S'), SG('S'), ST('B'), SR('V'), SY('B'), SK('B'), SM('V'), SS('S'), SW('N'), SB('B'), SD('N'), SH('N'), SV('V'), SN('N'),
     WA('W'), WC('H'), WG('D'), WT('W'), WR('D'), WY('H'), WK('D'), WM('H'), WS('N'), WW('W'), WB('N'), WD('D'), WH('H'), WV('N'), WN('N'), 
     BA('N'), BC('B'), BG('B'), BT('B'), BR('N'), BY('B'), BK('B'), BM('N'), BS('B'), BW('N'), BB('B'), BD('N'), BH('N'), BV('N'), BN('N'),
     DA('D'), DC('N'), DG('D'), DT('D'), DR('D'), DY('N'), DK('D'), DM('N'), DS('N'), DW('D'), DB('N'), DD('D'), DH('N'), DV('N'), DN('N'),
     HA('H'), HC('H'), HG('N'), HT('H'), HR('N'), HY('H'), HK('N'), HM('H'), HS('N'), HW('H'), HB('N'), HD('N'), HH('H'), HV('N'), HN('N'),
     VA('V'), VC('V'), VG('V'), VT('N'), VR('V'), VY('N'), VK('N'), VM('V'), VS('V'), VW('N'), VB('N'), VD('N'), VH('N'), VV('V'), VN('N'),
     NA('N'), NC('N'), NG('N'), NT('N'), NR('N'), NY('N'), NK('N'), NM('N'), NS('N'), NW('N'), NB('N'), ND('N'), NH('N'), NV('N'), NN('N');

     char consensusChar = 'X';

     lut(char c) {
         consensusChar = c;
     }

     char getConsensusChar() {
         return consensusChar;
     }
}

char getConsensus(char a, char b) {
    return lut.valueOf("" + a + b).getConsensusChar();
}
Источник

Простое, быстрое решение - использовать побитовое ИЛИ.

При запуске инициализируйте две таблицы:

  • Разреженная таблица из 128 элементов для сопоставления нуклеотида с одним битом. "Разреженный" означает, что вам нужно только указать элементы, которые вы будете использовать: коды IUPAC в верхнем и нижнем регистре.
  • 16-элементная таблица для сопоставления побитового консенсуса с нуклеотидным кодом IUPAC.

Чтобы получить консенсус по одной позиции:

  1. Используйте нуклеотиды в качестве индексов в первой таблице, чтобы получить побитовые представления.
  2. Побитовое ИЛИ побитовое представление.
  3. Используйте побитовое ИЛИ в качестве индекса в 16-элементной таблице.

Вот простое побитовое представление, чтобы вы начали:

    private static final int A = 1 << 3;
    private static final int C = 1 << 2;
    private static final int G = 1 << 1;
    private static final int T = 1 << 0;

Установите членов первой таблицы следующим образом:

    characterToBitwiseTable[ 'd' ] = A | G | T;
    characterToBitwiseTable[ 'D' ] = A | G | T;

Установите членов второй таблицы следующим образом:

    bitwiseToCharacterTable[ A | G | T ] = 'd';
Источник

Вы можете просто использовать HashMap<String, String> который сопоставляет конфликты / различия с согласованными символами. Вы можете либо "жестко кодировать" (ввести код своего приложения), либо заполнить его во время запуска приложения из какого-либо внешнего источника (файла, базы данных и т. Д.). Тогда вы просто используете его, когда у вас есть разница.

String consensusSymbol = consensusMap.get(differenceString);

РЕДАКТИРОВАТЬ: чтобы удовлетворить ваш запрос API;]

Map<String, Character> consensusMap; // let's assume this is filled somewhere
...
char getConsensus(char a, char b) {
    return consensusMap.get("" + a + b);
}

Я понимаю, что это выглядит грубо, но я думаю, вы поняли. Это может быть немного медленнее, чем справочная таблица, но также намного проще в обслуживании.

ДАЙТЕ ДРУГОЕ РЕДАКТИРОВАНИЕ:

Если вы действительно хотите что-то супер быстрое, и вы действительно используете char типа, вы можете просто создать 2d таблицу и индексировать ее с помощью символов (так как они интерпретируются как числа).

char lookup[][] = new char[256][256]; // all "english" letters will be below 256
//... fill it... e. g. lookup['A']['C'] = 'M';
char consensus = lookup['A']['C'];
Источник

Учитывая, что все они являются уникальными символами, я бы пошел на Enum:

public Enum ConsensusSymbol
{
    A("A"), // simple case
    // ....
    GTUC("B"),
    // etc
    // last entry:
    AGCTU("N");

    // Not sure what X means?

    private final String symbol;

    ConsensusSymbol(final String symbol)
    {
        this.symbol = symbol;
    }

    public String getSymbol()
    {
        return symbol;
    }
}

Затем, когда вы столкнулись с разницей, используйте .valueOf():

final ConsensusSymbol symbol;

try {
    symbol = ConsensusSymbol.valueOf("THESEQUENCE");
} catch (IllegalArgumentException e) { // Unknown sequence
    // TODO
}

Например, если вы столкнулись GTUC как строка, Enum.valueOf("GTUC") вернет GTUC перечислимое значение и вызов getSymbol() на это значение вернется "B",

Источник

Рассматривал чтение нескольких последовательностей одновременно - я бы:

  1. поместить все символы из одной и той же позиции в последовательности в набор
  2. сортировать и объединять значения в наборе и использовать enum.valueOf(), как в примере с fge
  3. использование приобретенного значения в качестве ключа к EnumMap, имеющему символы-символы в качестве значений

Возможно, есть способы оптимизировать второй и первый этапы.

Источник

Возможные комбинации - около 20. Таким образом, нет реальной проблемы с производительностью. Если вы не хотите делать большой блок if else, самым быстрым решением будет построение структуры данных Tree. http://en.wikipedia.org/wiki/Tree_data_structure. Это самый быстрый способ сделать то, что вы хотите сделать.

В дереве вы кладете все возможные комбинации и вводите строку, и она пересекает дерево, чтобы найти самую длинную последовательность для символа

Хотите иллюстрированный пример?

PS: Все программное обеспечение для искусственного интеллекта использует приложение Tree, которое является самым быстрым и наиболее адаптированным.

Источник
Другие вопросы по тегам