2

我有以下问题：

  • 我有 2 串 DNA 序列（由 ACGT 组成），它们在一两个点上有所不同。
  • 发现差异是微不足道的，所以让我们忽略它
  • 对于每个差异，我想获得代表两种可能性的共识符号（例如 A 或 C 的 M）

我知道我可以制作一个巨大的if 级联，但我想这不仅丑陋且难以维护，而且速度也很慢。

什么是一种快速、易于维护的方法来实现它？也许是某种查找表，或者组合的矩阵？任何代码示例将不胜感激。我会使用 Biojava，但我已经使用的当前版本不提供该功能（或者我还没有找到它......）。

更新：这里似乎有点混乱。共识符号是单个字符，代表两个序列中的单个字符。

例如，String1 和 String2 是“ACGT”和“ACCT”——它们在位置 2 上不匹配。所以，我想要一个共识字符串是 ACST，因为 S 代表“C 或 G”

我想做一个这样的方法：

char getConsensus(char a, char b)

更新 2：如果我只有 2 个序列，一些建议的方法可以工作。我可能需要对这些“共识”进行多次迭代，因此输入字母表可能会从“ACGT”增加到“ACGTRYKMSWBDHVN”，这会使一些提议的方法难以编写和维护。

4

6 回答 6

2

您可以只使用HashMap<String, String>将冲突/差异映射到共识符号的 a。您可以“硬编码”（填写您的应用程序的代码）或在您的应用程序启动期间从某些外部来源（文件、数据库等）填写它。然后，只要您有不同，您就可以使用它。

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类型，您可以创建一个二维表并用字符索引它（因为它们被解释为数字）。

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'];
于 2011-12-21T13:30:49.143 回答
2

一个简单、快速的解决方案是使用按位或。

在启动时，初始化两个表：

  • 将核苷酸映射到单个位的稀疏 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';
于 2011-12-21T15:50:12.017 回答
0

可能的组合在 20 左右。因此不存在真正的性能问题。如果你不想做一个大的 if else 块，最快的解决方案是构建一个 Tree 数据结构。http://en.wikipedia.org/wiki/Tree_data_structure。这是做你想做的事情的最快方法。

在树中，您放置所有可能的组合并输入字符串，然后遍历树以找到符号的最长匹配序列

你想要一个有插图的例子吗？

PS：所有人工智能软件都使用最快、最适应的树方法。

于 2011-12-21T13:15:49.603 回答
0

鉴于它们都是独特的符号，我会选择一个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"。

于 2011-12-21T13:16:42.397 回答
0

考虑一次读取多个序列 - 我会：

  1. 将序列中相同位置的所有字符放入一个集合
  2. 对集合中的值进行排序和连接，并使用 enum.valueOf() ，如 fge 的示例
  3. 获取的值用作具有一致性符号作为值的 EnumMap 的键

可能有一些方法可以优化第二步和第一步。

于 2011-12-21T14:31:38.677 回答
0

一个可能的使用枚举的解决方案，灵感来自 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();
}
于 2011-12-22T08:03:47.503 回答