gagro
2017-10-22 17:20:58 UTC
エラーのない読み取りからゲノムを組み立てる方法を理解しています。私は次のように実装しました：
2つの頂点間の最大オーバーラップとして読み取りを頂点として、エッジを使用して有向オーバーラップグラフを作成します。エッジは、1つの読み取りサフィックスと他の読み取りプレフィックスの最大部分文字列が重なる長さを表します。オーバーラップグラフで、すべての頂点に1回だけアクセスするパスを見つけます。小さなグラフでは、貪欲なアプローチを使用できます。最初のパターンから始めて、常に最大重みのegdeを選択し、このパスによってスペルされた最短の一般的なスーパーストリングを結果のストリングに格納します。パスで綴られた結果の文字列は、すべての読み取りの中で最も短い共通のスーパー文字列であり、アセンブルされたゲノムです。
たとえば
AACTAG CTAGAT 結果として AACTAGAT を提供します
ここで、エラーが発生しやすい2つの読み取りに最大で1つのエラー（不一致）があるとします。
AACTAG CTCGAT ご覧のとおり、2回目の読み取りでは、3番目の文字が 'A' から 'C' に1つ置換されています。
では、エラーが発生しやすい読み取りでは、アセンブルされたゲノムはどのように見える必要がありますか？結果の文字列に A または C を使用しますか？または、何かが足りませんか？
注：単純さのために、たとえば短い読み取りを使用しました。私は、100ヌクレオチドの長さで、文字の置換が1つしかない、はるかに多くの読み取りを処理します。これは大きなオーバーラップグラフです。 De Bruijnグラフを使用できることは知っていますが、貪欲なアプローチを使用できますか（エラーのない例のように）？