(57)【要約】コンピューティングサーバーは、identity-by-descent（IBD）ネットワークのようなグラフを生成する。グラフは複数のノードを含む。各ノードは、個体の１つを表す。２つ以上のノードは、エッジを介して接続されている。２つのノードを接続する各エッジは、２つのノードによって表される２つの個体の遺伝データの間の親和性に由来する重みに関連付けられる。コンピューティングシステムは、エッジまたはノードに関連付けられた特徴に基づいてグラフをフィルタリングする。フィルタリングされたグラフは、ノードのサブセットを含む。コンピューティングシステムは、フィルタリングされたグラフを複数のクラスターに分割し、フィルタリングなしでは発見できない可能性のある遺伝コミュニティを識別する。また、コンピューティングサーバーはノードによって表される個体を複数のコミュニティに割り当てるために、マルチパス階層コミュニティ検出処理を実行してもよい。
2021530026.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ実装方法であって、
複数の個体に対応する複数の遺伝データセットを引き出す工程と、
フルグラフを生成する工程であって、
前記フルグラフは複数のノードを備え、
各ノードは前記個体の１つを表し、
２つ以上の前記ノードがエッジを介して接続され、
各エッジが２つの前記ノードを接続し、前記２つのノードによって表される前記２つの個体の前記遺伝データセット間の親和性に由来する重みと関連付けられる工程と、
前記エッジまたは前記ノードに関連付けられた１つ以上の特徴に基づいて前記フルグラフをフィルタリングし、ノードのサブセットを備えた、フィルタリングされたグラフを生成する工程と、
前記フィルタリングされたグラフのノードのサブセットを、前記サブセット内の前記ノードを接続する前記エッジの重みに基づいて複数のクラスターに分割する工程であって、前記クラスターの各々は遺伝コミュニティを表す工程と、
を備える、コンピュータ実装方法。
【請求項２】
請求項１のコンピュータ実装方法であって、前記２つの個体の前記遺伝子データセット間の前記親和性が前記２つの個体の前記遺伝子データセットを比較することによって決定される、前記２人の個体の共有されたＩｄｅｎｔｉｔｙ-ｂｙ-ｄｅｓｃｅｎｃｅ（ＩＢＤ）遺伝子セグメント長に対応する、コンピュータ実装方法。
【請求項３】
請求項１のコンピュータ実装方法であって、前記フルグラフのフィルタリングが、前記エッジの特徴に基づいており、前記特徴が、各エッジに対して、前記エッジによって接続された２つのノードによって表される２つの個体の共通祖先の出生年の推定平均値に割り当てられた時間枠に対応する、コンピュータ実装方法。
【請求項４】
請求項３のコンピュータ実装方法であって、少なくとも１つのエッジに対する前記時間枠が、前記２つの個体の遺伝データセットを比較することによって決定される、前記２つの個体の共有されたＩｄｅｎｔｉｔｙ-ｂｙ-ｄｅｓｃｅｎｃｅ（ＩＢＤ）遺伝子セグメント長から決定される、コンピュータ実装方法。
【請求項５】
請求項３のコンピュータ実装方法であって、少なくとも１つのエッジに対する前記時間枠が、前記２つの個体の共有されたＩｄｅｎｔｉｔｙ-ｂｙ-ｄｅｓｃｅｎｃｅ（ＩＢＤ）遺伝セグメント長を入力として用いる機械学習モデルによって決定される、コンピュータ実装方法。
【請求項６】
請求項５のコンピュータ実装方法であって、前記機械学習モデルのトレーニングが、
ユーザーの遺伝データセットに基づいて、ユーザーのペアのうちの複数のペアがIBD共有の長さによってIBDに関連していることを識別する工程と、
前記ユーザーのペアの家系図データを取得する工程と、
ユーザーの各ペアが１つ以上の共通先祖を共有していることを決定する工程と、
出生年のデータが利用可能な前記共通祖先を特定する工程と、
前記共通祖先の前記出生年の時間枠と前記IBD共有の長さを含むトレーニングセットを生成する工程と、
前記トレーニングセットを用いて機械学習モデルをトレーニングする工程と
を備える、コンピュータ実装方法。
【請求項７】
請求項１のコンピュータ実装方法であって、前記フルグラフのフィルタリングが、前記ノードの特徴に基づいており、
前記特徴が、各ノードについて、前記ノードによって表される個体の遺伝データセットに対応し、
前記遺伝データセットが、対象となる民族性から遺伝する個体の遺伝セグメント長が閾値を超えることを示す、コンピュータ実装方法。
【請求項８】
請求項７のコンピュータ実装方法であって、前記対象となる民族性から遺伝する個体の遺伝セグメントの長さが、前記遺伝データセットと前記対象となる民族性の１つ以上の参照パネルサンプルとを比較することによって決定される、コンピュータ実装方法。
【請求項９】
請求項１のコンピュータ実装方法であって、前記フィルタリングされたグラフが第１のフィルタリングされたグラフであり、前記フルグラフのフィルタリングが、個体の民族構成要素において提示された第１の対象となる民族性に基づいており、前記コンピュータ実装方法は、
個体の民族構成要素において提示された第２の対象となる民族性に基づいてフルグラフをフィルタリングし、
第２のフィルタリングされたグラフを生成する工程であって、
前記第２のフィルタリングされたグラフ中の少なくとも１つのノードが前記第１のフィルタリングされたグラフ中にも存在する工程と、
をさらに備える、コンピュータ実装方法。
【請求項１０】
請求項１のコンピュータ実装方法であって、前記フィルタリングされたグラフのノードの前記サブセットを複数のクラスターに分割する工程は、前記フィルタリングされたグラフに複数のパーティションを定義する工程であって、各パーティションは候補となる遺伝コミュニティを表す工程と、
前記パーティションの因子を決定する工程であって、前記因子は同一のパーティションに分類された２つのノードを接続する前記エッジの前記重みに伴って増加し、あるパーティションのノードと別のパーティションのノードを接続するエッジの重みに伴って減少する値となる工程と、
前記因子の前記値を増加させるために前記複数のパーティションを調整する工程であって、調整されたパーティションは前記クラスターである工程と、
を備える、コンピュータ実装方法。
【請求項１１】
コンピュータ実装方法であって、
複数の個体に対応する複数の遺伝データセットを引き出す工程であって、前記複数の個体が混合された個体を含む工程と、
グラフを生成する工程であって、前記グラフは、
複数のノードを備え、
各ノードは前記個体の１つを表し、
２つ以上のノードはエッジを介して接続され、
各エッジは２つのノードを接続し、前記２つのノードによって表される前記２つの個体の前記遺伝データセット間の親和性由来する重みに関連付けられ、
前記複数のノードは、前記混合した個体を表す対象となるノードを含む工程と、
前記ノードを接続する前記エッジの前記重みに基づいて、前記グラフ内のノードを複数のクラスターに分割する工程であって、前記複数のクラスターは複数の遺伝コミュニティを表す、工程と、
１つ以上の遺伝コミュニティを表す１つ以上のクラスターに、前記対象となるノードを含める工程と、
前記対象となるノードが含まれる前記クラスターのうちの少なくとも１つに対して、
前記クラスターのうちの少なくとも１つを複数のサブクラスターに分割し、
前記対象となるノードを１つ以上のサブクラスターに分類する工程であって、
前記対象となるノードを１つ以上の異なるサブクラスターに分類することが、混合された個体が１つ以上の民族起源の、１つ以上の異なる遺伝サブコミュニティに分類されることを表す工程と、
を備える、コンピュータ実装方法。
【請求項１２】
請求項１１のコンピュータ実装方法であって、前記対象となるノードを１つ以上のクラスターに含める工程は、
前記対象となるノードが、閾値を超える対象となるクラスターに関して安定性を有するかどうかを決定する工程と、
前記閾値を超える前記安定性に応答して、前記対象となるクラスター内の対象となるノードを含む工程と
を備える、コンピュータ実装方法。
【請求項１３】
請求項１２のコンピュータ実装方法であって、前記対象となるノードが閾値を超える前記対象となるクラスターに関して前記安定性を有するかどうかを決定する工程は、
複数のノードのサブセットを生成する工程であって、ノードの各サブセットは前記グラフにおける前記複数のノードからサンプリングされ、ノードの各サブセットはサンプリングされたグラフを表す工程と、
前記サンプリングされたグラフの各々を第２の複数のクラスターに分割する工程であって、前記第２の複数のクラスターのうちの１つを、前記対象となるクラスターに対応させる工程と、
前記対象となるノードがサンプリングされた前記サンプリングされたグラフに対して、前記対象となるノードが前記対象となるクラスターに分類される回数を決定する工程と、
前記回数から、前記対象となるクラスターに対する前記対象となるノードの前記安定性を導出する工程と、
前記対象となるノードの前記安定性を前記閾値と比較する工程と、
を備える、コンピュータ実装方法。
【請求項１４】
請求項１１の記載のコンピュータ実装方法であって、前記グラフ内の前記ノードを複数のクラスターに分割する工程は、
前記グラフ内に複数のパーティションを定義する工程であって、各パーティションは候補の遺伝コミュニティを表す工程と、
前記パーティションの因子を決定する工程であって、前記因子は同じパーティションに分類された２つのノードを接続するエッジの重みに伴って増加する値となり、あるパーティションの前記ノードと別のパーティションの前記ノードを接続するエッジの重みに伴って減少する値となる工程と、
前記因子の前記値を増加させるために前記複数のパーティションを調整する工程であって、調整されたパーティションが前記クラスターである工程と、
を備える、コンピュータ実装方法。
【請求項１５】
請求項１１のコンピュータ実装方法であって、前記対象となるノードが含まれるクラスター毎に、前記クラスターを複数のサブクラスターに分割するのと同じクラスタリングアルゴリズムを用いて、前記グラフ内の前記ノードを複数のクラスターに分割する工程を備える、コンピュータ実装方法。
【請求項１６】
請求項１１のコンピュータ実装方法であって、前記２つの個体の遺伝データセット間の前記親和性が、前記２つの個体の前記遺伝データセットによって決定された前記２つの個体の共有されたＩｄｅｎｔｉｔｙ-ｂｙ-ｄｅｓｃｅｎｃｅ（ＩＢＤ）遺伝子セグメント長に対応する、コンピュータ実装方法。
【請求項１７】
請求項１１のコンピュータ実装方法であって、前記グラフが部分的に接続された無向グラフである、コンピュータ実装方法。
【請求項１８】
コンピュータ実装方法であって、
対象となる個体の遺伝データセットを引き出す工程と、
複数の参照パネルサンプルを引き出す工程であって、
各参照パネルサンプルは参照パネル個体を表し、
前記参照パネル個体の少なくとも一部は、フルＩＢＤネットワークからフィルタリングされたＩＢＤネットワークから生成され、
前記フルＩＢＤネットワークは複数のノードを備え、
各ノードは個体を表し、
２つ以上のノードはエッジを介して接続され、
各エッジは前記２つのノードを接続し、前記２つのノードによって表される前記２つの個体間のＩＢＤ親和性に由来する重みに関連付けられ、
前記フィルタリングされたＩＢＤネットワークは、前記エッジまたは前記ノードの１つ以上の特徴に基づいてフィルタリングされたノードのサブセットを含む工程と、
前記対象となる個体に関連付けられた複数のＩＢＤ親和性を生成する工程であって、各ＩＢＤ親和性は、前記対象となる個体の前記遺伝データセットを、前記参照パネルサンプルの１つと比較することによって決定される工程と、
コミュニティ分類器を引き出す工程であって、前記コミュニティ分類器は、個体が遺伝コミュニティに属しているかどうかを判断するように設定された機械学習モデルを備える工程と、
前記対象となる個体に関連付けられた特徴のセットを生成する工程であって、前記特徴のセットは、複数のＩＢＤ親和性に基づいて生成される工程と、
前記対象となる個体が前記遺伝コミュニティに属しているかどうかを判断するために、前記特徴のセットを前記コミュニティ分類器に入力する工程と、
前記対象となる個体が属する１つ以上の前記遺伝コミュニティを要約したレポートを生成する工程と、
を備える、コンピュータ実装方法。
【請求項１９】
請求項１８のコンピュータ実装方法であって、前記フィルタリングされたＩＢＤネットワークが、前記エッジの特徴に基づいてフィルタリングされ、前記特徴が各エッジに対して、前記エッジによって接続された前記２つのノードによって表される前記２つの個体の共通祖先の出生年の推定平均に割り当てられた時間枠に対応している、コンピュータ実装方法。
【請求項２０】
請求項１８のコンピュータ実装方法であって、前記フィルタリングされたＩＢＤネットワークが、前記ノードの特徴に基づいてフィルタリングされ、前記特徴が各ノードに対して、前記ノードによって表される前記個体の前記遺伝データセットに対応し、前記遺伝データセットが、対象となる民族から遺伝する前記個体の遺伝セグメント長が閾値を超えることを示す、コンピュータ実装方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的の個体群を発見する遺伝的ネットワークのフィルタリングに関する。
【背景技術】
【０００２】
本出願は、２０１８年６月１９日に出願された米国仮特許出願第６２／６８７１７７号の利益を主張し、これはその全体が参照により本明細書に組み込まれる。開示された実施形態は、発生および繁殖した可能性がある、目的の変異種の個体群を評価すること、および人々の間の遺伝的相関パターンから歴史上の個体群を発見することに関する。
【０００３】
人は、遺伝学的に言えば、ほぼ完全に同一であるが、人のDNAにおける僅かな差は、個体間で観測されるいくつかの変異が原因となっている。人のゲノムの突然変異率は、１世代あたり1.1×10-8と見込まれている。これは、約300の塩基対ごとに１変異種が生じるということになる。子孫に伝えられる突然変異のほとんどは、一塩基多型（SNP）に関連している。SNPとは、ゲノムの特定の位置で起こる１つのヌクレオチドの置換である。遺伝的多型データからから個体群の構造を学ぶことは、遺伝学の重要なトピックである。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願第１５／５９１０９９号明細書
【特許文献２】米国特許出願第１４／０２９７６５号明細書
【特許文献３】米国特許出願第１５／１６８０１１号明細書
【特許文献４】米国特許出願第１５／２０９４５８号明細書
【発明の概要】
【課題を解決するための手段】
【０００５】
本明細書で開示される方法は、個々人および個々人の間の遺伝的相関を示すグラフを描くこと、異なる個体群における新たな遺伝的コミュニティを発見すること、および１以上の遺伝的コミュニティが混合した個々人を割り当てることに関する。一実施形態では、コンピューティングサーバーは、複数の個体に対応する複数の遺伝的データセットを引き出すことを含む方法を実行する。コンピューティングサーバーは、フルグラフを表すデータを生成する。このフルグラフは、複数のノードを含む。各ノードは１つの個体、および対応する遺伝学的データセットを表す。２つ以上のノードは、エッジを介して接続される。エッジは２つのノードを接続し、２つのノードによって表される２つの個体の遺伝的データセット間の親和性に由来する重みに関連付けられている。コンピューティングサーバーは、エッジまたはノードに関連付けられた１つ以上の特徴に基づいて、フルグラフを表すデータをフィルタリングする。フィルタリングされたデータは、ノードのサブセットを備える、フィルタリングされたグラフを表す。コンピューティングサーバーは、フィルタリングされたグラフにおけるノードのサブセットを、サブセット内のノードを接続するエッジの重みに基づいた複数のクラスターに分割する。各クラスターは遺伝的コミュニティを表す。
【０００６】
別の実施形態では、コンピューティングサーバーは、複数の個体に対応する複数の遺伝的データセットを引き出す。個体のうちの１つは、混合した個体である。コンピューティングサーバーは、グラフを表すデータを生成する。グラフは、同様に、個体を表す複数のノードを含む。２つ以上のノードは、２つのノードによって表される２つの個体の遺伝的データセット間の親和性に由来する、重みに関連付けられるエッジを介して接続される。複数のノードは、混合された個体を表す対象となるノードと、他の個体を表す他の対象となるノードとを含む。コンピューティングサーバーは、グラフ中のノードを、ノードを接続するエッジの重みに基づいた複数のクラスターに分割する。複数のクラスターは、複数の遺伝的コミュニティを表す。コンピューティングサーバーは、対象となるノードを、１つ以上の遺伝的コミュニティを表す１つ以上のクラスター内に含む。対象となるノードが含まれるクラスターのうち少なくとも１つに対して、コンピューティングサーバーは、クラスターを複数のサブクラスターに分割する。対象となるノードは、１つ以上のクラスターの各々において、１つ以上のサブクラスターに分類されてもよい。これは、混合された個体が、１つ以上の民族起源の１つ以上の異なる遺伝的サブコミュニティに分類されていることを表す。
【０００７】
さらに別の実施形態では、コンピューティングサーバーは、対象となる個体の遺伝データセットを引き出す。コンピューティングサーバーは、複数の参照パネルのサンプルを引き出す。各参照パネルのサンプルは、参照パネルの個体を表す。参照パネルの個体の少なくとも一部は、フルIBDネットワークからフィルタリングされたIBDネットワークから生成される。フィルタリングされたIBDネットワークは、エッジまたはノードの１つ以上の特徴に基づいてフィルタリングされたノードのサブセットを含む。コンピューティングサーバーは、対象となる個体に関連付けられた複数のIBDの親和性を生成する。各IBDの親和性は、対象となる個体の遺伝的データセットを参照パネルのサンプルの１つと比較することによって決定される。コンピューティングサーバーは、１つ以上のコミュニティ分類子を引き出す。各コミュニティ分類子は、個体が遺伝的コミュニティに属しているかどうかを決定するために設定されたモデルである。コンピューティングサーバーは、各コミュニティ分類子に対する特徴のセットを生成する。特徴のセットは、複数のIBDの親和性に基づいて生成されてもよい。コンピューティングサーバーは、対象となる個体が遺伝的コミュニティに属しているかどうかを決定するために、コミュニティ分類器ごとに、特徴量のセットをコミュニティ分類器に入力する。コンピューティングサーバーは、対象となる個体が属する１つ以上の遺伝的コミュニティをまとめたレポートを生成する。
【図面の簡単な説明】
【０００８】
【図１】一実施形態による、例示的なコンピューティングシステムのシステム環境の図である。
【図２】一実施形態による、例示的なコンピューティングシステムのアーキテクチャのブロック図である。
【図３Ａ】一実施形態による、例示的なIdentity-by-Descent（IBD）ネットワークを示す図である。
【図３Ｂ】一実施形態による、例示的なIdentity-by-Descent（IBD）ネットワークを示す図である。
【図４】一実施形態による、IBDネットワークをフィルタリングする、例示的なプロセスを示すフローチャートである。
【図５】一実施形態による、フィルタリングされたＩＢＤネットワークの例を示す図である。
【図６】一実施形態による、２人の個体の共通祖先の出生年を、時間枠に分類する処理の例を示すブロック図である。
【図７Ａ】シングルパスのコミュニティ検出プロセスのための樹形図である。
【図７Ｂ】一実施形態による、マルチパスコミュニティ検出プロセスのための樹形図である。
【図８】一実施形態による、マルチパスコミュニティ検出を実行する、例示的なプロセスを示すフローチャートである。
【図９】一実施形態による、マルチパス階層コミュニティ検出アプローチを示す図である。
【図１０】一実施形態による、個体の先祖代々の構成要素を検出する、例示的なプロセスを示すフローチャートである。
【図１１】一実施形態による、例示的なコンピューティングデバイスのブロック図である。
【０００９】
図は、説明のみを目的とするため、様々な実施形態を示している。当業者は、本明細書に例示された構造および方法の代替的な実施形態が、本明細書に記載された原理から逸脱することなく採用され得ることを、以下の議論から容易に認識するであろう。
【発明を実施するための形態】
【００１０】
システム環境の例
図１は、一実施形態による、例示的なコンピューティングサーバー１３０のシステム環境１００の図を示している。図１に示されるシステム環境１００は、１つ以上のクライアントデバイス１１０、ネットワーク１２０、遺伝データ抽出サービスサーバー１２５、およびコンピューティングサーバー１３０を含む。いくつかの実施例においては、システム環境１００は、より少ない、または追加のコンポーネントを含んでもよい。また、システム環境１００は、異なるコンポーネントを含んでもよい。
【００１１】
クライアントデバイス１１０は、ネットワーク１２０を介してデータを送信および／または受信するだけでなく、ユーザーの入力を受信することができる１つ以上のコンピューティングデバイスである。例示的なコンピューティングデバイスは、デスクトップコンピューター、ラップトップコンピューター、パーソナルデジタルアシスタント（PDA）、スマートフォン、タブレット、ウェアラブル電子デバイス（例えば、スマートウォッチ）、スマート家電（例えば、スマートテレビ、スマートスピーカー、スマートホームハブ）、モノのインターネット（IoT）デバイス、または他の適切な電子デバイスを含む。クライアントデバイス１１０は、ネットワーク１２０を介して他のコンポーネントと通信する。一実施形態では、クライアントデバイス１１０は、クライアントデバイス１１０のユーザーがクライアントデバイスのユーザーインターフェイス１１５を介し、コンピューティングサーバー１３０と相互作用するためのグラフィカルユーザーインターフェイス（GUI）を起動するアプリケーションを実行する。例えば、クライアントデバイス１１０は、ネットワーク１２０を介してクライアントデバイス１１０とコンピューティングサーバー１３０との間の相互作用を可能にするために、Webブラウザアプリケーションを実行してもよい。別の実施形態では、ユーザーインターフェイス１１５は、コンピューティングサーバー１３０によって発行され、ユーザーデバイス１１０にインストールされるソフトウェアアプリケーションの形態をとってもよい。さらに別の実施形態では、クライアントデバイス１１０は、IOSまたはANDROIDなどのクライアントデバイス１１０のネイティブオペレーティングシステム上で実行されるアプリケーションプログラミングインターフェイス（API）を介して、コンピューティングサーバー１３０と相互作用する。
【００１２】
ネットワーク１２０は、１つ以上のサブネットワークを介してシステム環境１００のコンポーネントへの接続を提供し、サブネットワークは、ローカルエリアおよび／または広域ネットワークの任意の組み合わせを含んでもよい。一実施形態においては、ネットワーク１２０は、標準的な通信技術および／またはプロトコルを用いる。例えば、ネットワーク１２０は、イーサネット802.11、Worldwide Interoperability for Microwave Access(WiMAX)、3G、4G、Long Term Evolution(LTE)、5G、符号分割多元接続(CDMA)、デジタル加入者回線(DSL)などの技術を使用した通信リンクを含んでもよい。ネットワーク１２０を介して通信するために使用されるネットワークプロトコルの例としては、Multi-Protocol Label Switching（MPLS）、Transmission Control Protocol/Internet Protocol (TCP/IP)、HyperText Transfer Protocol（HTTP）、Simple Mail Transfer Protocol (SMTP)、File Transfer Protocol (FTP)などが挙げられる。ネットワーク１２０を介して交換されるデータは、HyperText Markup Language（HTML）またはExtensible Markup Language（XML）などの任意の適切なフォーマットを使用して表現されてもよい。いくつかの実施形態では、ネットワーク１２０の通信リンクの全てまたは一部は、任意の適切な技術、またはSecure Sockets Layer（ＳＳＬ）、Transport Layer Security (TLS)、Virtual Private Networks (VPN)、Internet Protocol Security (IPsec)などのような技術を用いて暗号化されてもよい。ネットワーク１３０は、インターネットのようなリンクおよびパケット交換ネットワークも含む。
【００１３】
コンピューティングサーバー１３０を運営する企業の顧客であり得る個体は、遺伝データの分析のために生体サンプルを提供する。一実施形態においては、個体は増幅および配列決定などのヌクレオチド処理技術により、遺伝データが抽出される生体サンプル（例えば、唾液、血液、毛髪、組織）を提供するために、サンプル収集キットを用いる。増幅は、ヌクレオチドサンプルのセグメントを増幅することができる、ポリメラーゼ連鎖反応（PCR）の使用を含んでもよい。配列決定は、デオキシリボ核酸（DNA）配列決定、リボ核酸（RNA）配列決定等の配列決定を含んでもよい。ヌクレオチドサンプルの配列決定は、サンガー法、全ゲノムシーケンス、パイロシーケンス、合成による配列決定、ライゲーションによる配列決定、イオン半導体配列決定などの各種次世代配列決定（NGS）技術のような大規模並列配列決定を含んでもよい。遺伝データ抽出サービスサーバー１２５は、コンピューティングサーバー１３０のユーザーから生体サンプルを受信する。遺伝データ抽出サービスサーバー１２５は、生体サンプルの配列決定を行い、個体の塩基対配列を決定する。遺伝データ抽出サービスサーバー１２５は、配列決定の結果に基づいて、個体の遺伝データを生成する。遺伝データは、DNAまたはRNAから配列決定されたデータを含んでもよく、DNAの発現領域および／または非発現領域からの塩基対を含んでもよい。
【００１４】
遺伝データは、異なる形態をとってもよい。例えば、一実施形態では、遺伝データは、個体の塩基対配列であってもよい。塩基対配列は、ゲノム全体、または目的の遺伝子座のようにゲノムの一部を含んでもよい。別の実施形態では、遺伝データ抽出サービスサーバー１２５は、遺伝データのデータ前処理を実行して、塩基対の生の配列を対象となるSNPサイトの遺伝子型の配列に変換してもよい。この例における結果は、様々なSNPサイト対応する遺伝子型の配列を含んでもよい。一実施形態では、遺伝データ抽出サービスサーバー１２５は、塩基対の生の配列を対象となるSNPサイトの遺伝子型の配列に変換するため、遺伝データのデータ前処理を実行してもよい。典型的なヒトゲノムは、数百万のSNPサイトのみで参照ヒトゲノムと異なる場合があるので（全ゲノムにおける数十億の塩基対とは対照的に）、遺伝データ抽出サービスサーバー１２５は、一組の対象となるSNPサイトにおける遺伝子型のみを抽出し、抽出されたデータを個体の遺伝データセットとしてコンピューティングサーバー１３０に送信してもよい。
【００１５】
コンピューティングサーバー１３０は、遺伝データの様々な分析を実行し、コンピューティングサーバー１３０のユーザーの遺伝および家系に関する結果を生成する。実施形態によっては、コンピューティングサーバー１３０は、オンラインサーバー、個体遺伝サービスサーバー、家系サーバー、家系図構築サーバー、および／またはソーシャルネットワーキングシステムとしても参照され得る。実施形態によっては、コンピューティングサーバー１３０は、遺伝データ抽出サービスサーバー１２５から遺伝データを受信し、コンピューティングサーバー１３０のデータストアに遺伝データを格納する。ユーザーの遺伝および家系に関する結果は、ユーザーの民族組成、父方および母方の遺伝分析、潜在的な家族関係、先祖情報、DNAデータの分析、ユーザーの潜在的または識別された表現型（例えば、病気、形質、および他の特徴）などを含んでもよい。コンピューティングサーバー１３０は、クライアントデバイス１１０に表示されたGUIを介してユーザーに結果を提示するようユーザーインターフェイス１１５を提示してもよいし、させてもよい。結果は、グラフィカル要素、テキスト情報、データ、および血統書を含む家系図などの他の要素を含んでもよい。
【００１６】
一実施形態では、コンピューティングサーバー１３０は、様々なユーザーがそのユーザーの１つ以上の家系プロファイルを作成することを可能にする。家系プロファイルは、ユーザーによって追加または選択され、家系記録および／または遺伝記録に基づいてコンピューティングサーバー１３０によって提示される個体（例えば、先祖、親戚、友人、および関心のある他の人々）のリストを含んでもよい。コンピューティングサーバー１３０と通信して制御されるユーザーインターフェイス１１５は、個体をリストで、または血統書の形式などの家系図として表示してもよい。一実施形態では、ユーザーのプライバシー設定および承認を条件として、コンピューティングサーバー１３０は、ユーザーの遺伝データセットがユーザープロファイルおよび１つ以上の家系図にリンクされることを許可してもよい。また、ユーザーは、コンピューティングサーバー１３０がそのユーザーの遺伝データセットを分析することを許可してもよい。
【００１７】
コンピュータサーバの構造例
図２は、一実施形態による例示的なコンピューティングサーバー１３０のアーキテクチャのブロック図である。図２に示す実施形態では、コンピューティングサーバー１３０は、家系データストア２０５、遺伝データストア２１０、サンプルプリプロセッシングエンジン２１５、フェージングエンジン２２０、ＩＢＤ推定エンジン２２５、コミュニティアサイメントエンジン２３０、ＩＢＤネットワークデータストア２３５、参照パネルサンプルストア２４０、民族性推定エンジン２４５、およびフロントエンドインターフェイス２５０を含む。コンピューティングサーバー１３０の機能は、説明とは異なる方法で要素間に分散されてもよい。様々な実施形態では、コンピューティングサーバー１３０は、異なるコンポーネントと、より少ないまたは追加のコンポーネントとを含んでもよい。様々なデータストアの各々は、単一のストレージデバイス、複数のストレージデバイスを制御するサーバー、または複数のノード（例えば、クラウドストレージシステム）を介してアクセス可能な分散ネットワークであってもよい。
【００１８】
コンピューティングサーバー１３０は、ユーザーの遺伝データを処理して、個体間で共有されるＩＢＤセグメントを特定する。コンピューティングサーバー１３０は、遺伝データおよび家系データを含む、異なる個体の様々なデータを格納する。コンピューティングサーバー１３０は、ユーザープロファイルデータを含む家系データを家系データストア２０５に保持する。家系データストア２０５中で各ユーザーに対して保存されるユーザープロファイルデータの量および種類は、ユーザーに対応する提供情報に基づいて変化してもよい。ユーザーは、クライアント装置１１０のユーザーインターフェイス１１５を介してデータを提供してもよい。例えば、ユーザーは、ユーザーインターフェイスのグラフィカル要素において、ユーザーに関連する質問、および他の家系データおよび調査データを得るために処理され得る基本情報に答えるように、プロンプトされてもよい。家系データの例としては、名前（名、姓、中間、接尾辞）、性別、出生地、出生日、死亡日、結婚情報、配偶者情報の親族関係、家族歴、ライフイベント（例えば、出生および死亡）の日付および場所、その他のバイタルデータなどが挙げられる。いくつかの実施形態では、家族歴は、その個体の血統書（例えば、記録された家族内の関係）の形をとることができる。ユーザーに関連付けられた血統情報は、１つ以上の指定されたノードを含む。血統書の各ノードは、その個体、その個体に遺伝物質を受け継いだ可能性のあるその個体の先祖、および場合によっては子孫のようなその個体の他の親族を表す。家系データは、コンピューティングサーバー１３０のユーザー間の遺伝的な接続を含んでもよい。
【００１９】
ユーザーが入力するデータに加え、系図データは、公的記録や第三者のデータ収集者といった様々な情報源から得られる他の形態をとってもよい。例えば、公的な情報源から得られる家系データとしては、出生記録、結婚記録、死亡記録、国勢調査記録、裁判所記録、検認記録、養子縁組記録、死亡記録等が挙げられる。調査データの形態における家系データは、人の身体的形質（例えば、身長、髪の毛、皮膚の色素沈着、そばかす、苦味、耳たぶのタイプ、虹彩のパターン、男性型脱毛症、髪のカール）、ウェルネス表現型（例えば、乳糖耐性、カフェイン摂取量、マラリア耐性、ノロウイルス耐性、筋力、アルコールフラッシュ）、個人的嗜好（例えば、好き嫌い）などの表現型に関する情報を含む。さらに、家系データストア２０５は、遺伝データストア２１０に格納されている遺伝サンプルから推定される情報と、個体から受信した情報とを含んでもよい。例えば、どの個体が遺伝的に関連しているか、どのように関連しているか、何世代前に共通先祖を共有しているか、共有されているIBDセグメントの長さおよび位置、個体がどの遺伝コミュニティの一部であるか、個体によって担われている亜種、などに関する情報が挙げられる。
【００２０】
加えて、家系データは、個体の血統書、Ancestry World Treeシステム、Social Security Death Indexデータベース、World Family Treeシステム、出生証明書データベース、死亡証明書データベース、結婚証明書データベース、養子縁組データベース、徴兵登録データベース、退役軍人データベース、軍人データベース、財産記録データベース、国勢調査データベース、有権者登録データベース、電話データベース、住所データベース、新聞データベース、入国管理データベース、家族歴史記録データベース、地域歴史記録データベース、事業者登録データベース、自動車データベースなどのうちの１つ以上のデータを含んでよい。
【００２１】
コンピューティングサーバー１３０は、個体の遺伝データセットを遺伝データストア２１０に保持する。個体の遺伝データセットは、ヌクレオチドデータおよび対応するメタデータのデジタルデータセットであってもよい。データは、個体のゲノムの全体または一部を含んでいてもよい。また、遺伝データストア２１０は、個体に関連付けられた家系データストア２０５に関連付けられた場所へのポインタを格納してもよい。遺伝データセットは、別の形態をとってもよい。一実施形態では、遺伝データセットは、個体の配列決定結果の塩基対配列の形態をとってもよい。塩基対配列データセットは、個体の全ゲノム（例えば、全ゲノム配列決定から得られた）またはゲノムの一部（例えば、目的の遺伝子座）を含んでもよい。
【００２２】
別の実施形態では、遺伝データセットは、配列決定結果からフィルタリングされた対象となるSNPサイト（例えば、対立遺伝子サイト）の配列の形態をとってもよい。また、対象となるSNPサイトは、一意の識別子と関連づけられた遺伝マーカーと呼ばれてもよい。遺伝データセットは、対象となるSNPサイトの遺伝子型など、遺伝子型の配列決定を含む二倍体データの形態であってもよいし、対象となるSNPサイトの遺伝子型およびSNPと一般的に関連しない他の塩基対サイトの遺伝子型を含む塩基対配列全体の配列決定を含む、二倍体データの形態であってもよい。二倍体データセットは、遺伝子型データセットと称してもよい。個体の遺伝子型は、個体の二倍体対立遺伝子配列の集合体を参照してもよい。他の状況では、遺伝子型は、SNPサイトのような与えられた遺伝的マーカーにおいて、ある個体の２本の染色体上に存在する対立遺伝子のペアとしてもよい。
【００２３】
このように、SNPサイトにおける各遺伝子型は、対立遺伝子の対を含んでいてもよい。対立遺伝子の対は、ホモ接合体（例えば、Ａ-ＡまたはＧ-Ｇ）またはヘテロ接合体（例えば、Ａ-Ｔ、Ｃ-Ｔ）であってもよい。実際のヌクレオチドを格納する代わりに、遺伝データストア２１０は、ビットに変換された遺伝データを格納してもよい。多くのSNPサイトでは、２つのヌクレオチド対立遺伝子のみ（４個すべてではなく）が観察される。このように、２ビットのナンバーは、SNPサイトを表してもよい。例えば、００はホモ接合性の第１対立遺伝子を表してもよく、１１はホモ接合性の第２対立遺伝子を表してもよく、０１または１０はヘテロ接合性の対立遺伝子を表してよい。別個のライブラリーは、所定のSNPサイトにおいて、第１の対立遺伝子に対応するヌクレオチドおよび第２の対立遺伝子に対応するヌクレオチドを格納してもよい。
【００２４】
また、二倍体データセットは、第１の親側に対応するものと第２の親側に対応するものとの２セットのハプロタイプデータセットに段階的に分割されてもよい。段階的に分割されたデータセットは、ハプロタイプデータセットと呼んでよい。
【００２５】
一実施形態では、遺伝データストア２１０は、個体がキャリアである既知のバリアントに関する情報（例えば、バリアントのタイプ、バリアントの位置、バリアントに関連する表現型）を追加で含んでもよい。この情報は、コンピューティングサーバー１３０、第三者データベース、または第三者ソフトウェアを使用して得られることができる。
【００２６】
サンプルプリプロセッシングエンジン２１５は、データをコンピューティングサーバー１３０が用いたフォーマットに変更するため、様々なソースから受信したデータの受信、および前処理を行う。家系データに対しては、サンプルプリプロセッシングエンジン２１５は、クライアントデバイス１１０のユーザーインターフェイス１１５を介して個体からデータを受信する。ユーザーデータ（例えば、家系データおよび調査データ）を収集するため、コンピューティングサーバー１３０は、ユーザーが家系データおよび調査データを提供することができるインターフェイス要素を表示する、クライアントデバイス１１０上の対話型ユーザーインターフェイスを引き起こしてもよい。これらのデータは、手動で提供されてもよいし、例えば、国勢調査記録、町または政府の記録、または印刷またはオンライン材料の任意の他の項目に対して実行される光学的文字認識（OCR）を介して自動的に抽出されてもよい。いくつかの記録は、古い国勢調査記録、出生証明書、死亡証明書などのような書かれた記録をデジタル化することによって得られてもよい。
【００２７】
また、サンプルプリプロセッシングエンジン２１５は、遺伝データ抽出サービスサーバー１２５から生データを受信してもよい。遺伝データ抽出サービスサーバー１２５は、ユーザーの生体サンプルの実験的分析を行い、デジタルデータの形で配列決定結果を生成してもよい。サンプルプリプロセッシングエンジン２１５は、遺伝データ抽出サービスサーバー１２５から生の遺伝データセットを受信してもよい。サンプルプリプロセッシングエンジン２１５は、生の塩基対配列を、対象となるSNPサイトの遺伝子型の配列に変換してもよい。あるいは、この変換の前処理は、遺伝データ抽出サービスサーバー１２５によって実行されてもよい。サンプルプリプロセッシングエンジン２１５は、個体の遺伝データセット内の常染色体性SNPを同定する。例えば、700,000個の常染色体SNPが個体のデータ内で同定され、遺伝データストア２１０に格納されてもよい。あるいは、一実施形態においては、遺伝データセットは、少なくとも10,000個のSNPサイトを含んでもよい。別の実施形態においては、遺伝データセットは、少なくとも100,000個のSNPサイトを含んでもよい。さらに別の実施形態では、遺伝学的データセットは、少なくとも500,000個のSNPサイトを含んでもよい。さらに別の実施形態では、遺伝的データセットは、少なくとも1,000,000個のSNPサイトを含んでもよい。また、サンプルプリプロセッシングエンジン２１５は、ヌクレオチドをビットに変換してもよい。ビットまたは他の適切なフォーマットで同定されたSNPは、各ユーザーに対する一対のハプロタイプを生成するために、個体の二倍体遺伝子型をフェージングするフェージングエンジン２２０に提供さてもよい。
【００２８】
フェージングエンジン２２０は、二倍体遺伝データセットを一対のハプロタイプ遺伝データセットにフェージングする。個体のハプロタイプは、両親から受け継いだ対立遺伝子のセット（例えば、対立遺伝子の配列）を参照してもよい。また、ある状況では、ハプロタイプは遺伝セグメントにおける特定の突然変異に対応する対立遺伝子のセットを参照してもよい。更に、他の状況においては、ハプロタイプは、SNPサイトにおける特定の対立遺伝子を参照してもよい。例えば、ハプロタイプの配列は、両親から遺伝する個体の配列対立遺伝子の塩基対を参照してもよい。
【００２９】
フェージングは、染色体への対立遺伝子（特にヘテロ接合性対立遺伝子）の割り当てを決定するプロセスを含んでもよい。配列決定条件および他の制約のために、配列決定結果は、しばしば、一対の染色体の所定のSNPサイトにおける一対の対立遺伝子に関するデータを含むが、どの対立遺伝子がどの特定の染色体に属するかを区別できない場合がある。フェージングエンジン２２０は、遺伝子型フェージングアルゴリズムを使用して、ある対立遺伝子を第１の染色体に割り当て、別の対立遺伝子を別の染色体に割り当てる。遺伝子型フェージングアルゴリズムは、対立遺伝子の配列の形態をしたハプロタイプが一緒にクラスタリングする傾向があるという連鎖不平衡（LD）の仮定に基づいて開発されてもよい。フェーシングエンジン２２０は、他の多くのサンプルにおいても一般的に観察されるフェージングされた配列を生成するように構成されている。別の言い方をすれば、異なる個体のハプロタイプ配列は、一緒にクラスター化する傾向がある。ハプロタイプ-クラスターモデルは、対立遺伝子の配列を含むハプロタイプの確率分布を決定するために生成されてもよい。ハプロタイプ-クラスターモデルは、両親と子のトリオからの既知のフェージングハプロタイプを含むラベル付けされたデータに基づいてトレーニングされてもよいが、これは、子の遺伝子型と親の遺伝データセットとを比較することにより、正確な子のフェージングハプロタイプがほぼ確実であるからである。また、ハプロタイプ-クラスターモデルは、多数のフェージングされていない遺伝子型データセットを用いて、フェージングプロセスと並行して反復的に生成されてもよい。
【００３０】
一例として、フェーシングエンジン２２０は、対象となる遺伝子型データセットのフェージングを行うために、隠れマルコフモデル（ＨＭＭ）のような有向非巡回グラフモデルを用いてもよい。有向非巡回グラフは、複数のレベルを含んでもよく、各レベルは、ハプロタイプクラスターの異なる可能性を表す複数のノードを有する。また、ある遺伝子型の観測から特定のハプロタイプクラスターを持つ確率を表すノードの放出確率は、ハプロタイプ-クラスターモデルの確率分布に基づいて決定されてもよい。あるノードから別のノードへの遷移確率は、最初は0以外の値に割り当てられ、有向非巡回グラフモデルとハプロタイプ-クラスターモデルがトレーニングされるにつれて調整されてもよい。有向非巡回グラフモデルの異なるレベルをトラバースする際には、様々なパスが可能である。フェージングエンジン２２０は、遷移確率および放出確率に基づいて、最も確率の高いパス、または他の可能性のあるパスの少なくとも95％以上の可能性があるパスのような、統計的に確率の高いパスを決定する。ビタビアルゴリズムのような適切な動的プログラミングアルゴリズムは、パスを決定するために用いられてもよい。決定されたパスは、フェージング結果を表してもよい。特許文献１は、ハプロタイプフェージングの可能な一実施形態を述べている。
【００３１】
IBD推定エンジン２２５は、遺伝データストア２１０に格納されているフェージングされた遺伝子型データ（例えば、ハプロタイプデータセット）に基づいて、一対の個体間で共有されている遺伝セグメントの量を推定する。IBDセグメントとは、共通祖先からの遺伝があるとされる個体のペアで特定された染色体セグメントである。IBD推定エンジン２２５は、各個体について一対のハプロタイプデータセットを引き出す。IBD推定エンジン２２５は、各ハプロタイプデータセット配列を複数のウィンドウに分割してもよい。各ウィンドウは、固定数のSNPサイト（例えば、約100個のSNPサイト）を含む。IBD推定エンジン２２５は、２つの個体間のフェージングハプロタイプのうちの少なくとも１つに含まれるすべてのSNPサイトにおける対立遺伝子が同一である、１つ以上のシードウィンドウを特定する。IBD推定エンジン２２５は、一致したウィンドウが染色体の端に達するまで、またはホモ接合性不一致が見出されるまで、シードウィンドウから近くのウィンドウへと一致を拡大してもよく、これは不一致がフェージングにおける潜在的な誤差に起因しないことを示す。IBD推定エンジン２２５は、一致したセグメントの全長を決定し、これはＩＢＤセグメントと呼ばれてよい。長さは、センチモルガン（cM）単位の遺伝的距離で測定される。コンピューティングサーバー１３０は、家系データストア２０５のように、所定の閾値（例えば、６cM）を超えるIBDセグメントの長さを共有する個々のペアに関するデータを保存してもよい。特許文献２には、IBD推定の例示的な実施形態が述べられている。
【００３２】
一般に、近親者は比較的多くのIBDセグメントを共有しており、IBDセグメントの長さが長くなる傾向がある（個々、または１つ以上の染色体の集合体で）。対照的に、遠縁関係にある人は、IBDセグメントの数が比較的少なく、セグメントの長さが短い傾向がある（個々、または１つ以上の染色体の集合体で）。例えば、近親者（３番目のいとこなど）は71cM以上のIBDを共有していることが多いのに対し、遠縁者は12cM以下のIBDを共有し得る。２つの個体間のIBDセグメントの観点における関連性の程度は、IBD親和性と呼ぶこともできる。例えば、IBD親和性は、２つの個体間のIBDセグメントの長さという観点で測定されてもよい。
【００３３】
コミュニティアサイメントエンジン２３０は、個体を１つ以上の遺伝コミュニティに割り当てる。遺伝コミュニティは、民族由来であってもよい。遺伝コミュニティの分類の粒度は、コミュニティを割り当てる際に使用される実施形態および方法に応じて変化してもよい。例えば、一実施形態においては、コミュニティは、アフリカ系、アジア系、ヨーロッパ系などであってもよい。別の実施形態では、ヨーロッパのコミュニティは、アイルランド人、ドイツ人、スウェーデン人などに分けられてもよい。さらに別の実施形態では、アイルランド人は、アイルランドのアイルランド人、１８００年にアメリカに移住したアイルランド人、１９００年にアメリカに移住したアイルランド人など、さらに分けられてもよい。また、コミュニティの分類は、人口が混同されているか混同されていないかに依存してもよい。混同された人口の場合は、地理的な地域における異なった民族性に基づいて、さらに分類を分けることができる。
【００３４】
コミュニティアサイメントエンジン２３０は、教師なし学習または教師あり学習によってトレーニングされた機械学習モデルを使用して、遺伝的データセットに基づいて、個体を１つ以上の遺伝的コミュニティに割り当ててもよい。教師なしのアプローチでは、コミュニティアサイメントエンジン２３０は、部分的に接続された無向グラフを表すデータを生成してもよい。このアプローチでは、コミュニティアサイメントエンジン２３０は、個体をノードとして表す。一部のノードは、ノードによって表される２つの個体間のIBD親和性に基づいて重みが設定されているエッジによって接続される。例えば、２つの個体の共有IBDセグメントの全長が所定の閾値を超えない場合、ノードは接続されない。２つのノードを接続するエッジは、IBD親和性に基づいて測定される重みに関連付けられる。無向グラフは、IBDネットワークと呼ぶこともできる。コミュニティアサイメントエンジン２３０は、モジュール性測定などのクラスタリング技術を用いて、ノードをIBDネットワーク内の異なるクラスターに分類する。各クラスターは、コミュニティを表してもよい。また、コミュニティアサイメントエンジン２３０は、サブコミュニティを表すサブクラスターを決定してもよい。コンピューティングサーバー１３０は、IBDネットワークおよびクラスターを表すデータをIBDネットワークデータストア２３５に保存する。特許文献３は、コミュニティ検出および割り当ての可能な一実施形態を述べている。
【００３５】
また、コミュニティアサイメントエンジン２３０は、教師付き技術を用いてコミュニティを割り当ててもよい。例えば、既知の遺伝コミュニティ（例えば、民族起源が確認された個体）の遺伝データセットを、遺伝コミュニティのラベル付けがなされたトレーニングセットとして用いてもよい。ロジスティック回帰器、サポートベクターマシン、ランダムフォレスト分類器、ニューラルネットワークなどの教師付き機械学習分類器は、ラベルが付けられたトレーニングセットを用いてトレーニングされてもよい。トレーニングされた分類器は、バイナリまたは複数のクラスを区別してもよい。例えば、バイナリ分類器は、目的のコミュニティ毎にトレーニングされ、対象となる個体の遺伝データセットが目的のコミュニティに属するか否かを判断し得る。ニューラルネットワークのような複数クラスの分類器もまた、対象となる個体の遺伝データセットが、最も可能性の高いいくつかの遺伝コミュニティのうちの１つに属するかどうかを決定するためにトレーニングされてもよい。
【００３６】
参照パネルサンプルストア２４０は、異なる遺伝コミュニティに対する参照パネルサンプルを格納する。ある個体の遺伝データは、ある遺伝コミュニティの中で最も代表的なものとなり得る。これらの遺伝データセットは、参照パネルサンプルとして機能することができる。例えば、遺伝子の対立遺伝子の中には、ある遺伝コミュニティにおいて過剰に代表的な（例えば、非常に一般的である）ものがあり得る。遺伝データセットの中には、そのコミュニティのメンバーの間で、一般的に存在する対立遺伝子が含まれているものもある。参照パネルサンプルは、対象となる遺伝データセットがコミュニティに属するかどうかを分類する際、個体の民族構成を決定する際、および分類器からの分類結果の事後確率を計算することによってなど、任意の遺伝データ分析における精度を決定する際に、様々な機械学習モデルをトレーニングするために用いることができる。
【００３７】
参照パネルサンプルは、異なる方法で識別されてもよい。一実施形態では、コミュニティ検出における教師なしのアプローチは、サブクラスターが閾値よりも小さいノードの数（例えば、1,000ノードよりも少ないノードを含む）を含むまで、識別された各クラスターに対してクラスタリングアルゴリズムを再帰的に適用してよい。例えば、コミュニティアサイメントエンジン２３０は、ノードによって表される個体のセットを含むフルIBDネットワークを構築し、クラスタリング技術を用いてコミュニティを生成してもよい。コミュニティアサイメントエンジン２３０は、サンプルされたIBDネットワークを生成するために、ノードのサブセットをランダムにサンプリングしてよい。コミュニティ割り当てエンジン２３０は、サンプリングされたＩＢＤネットワーク内のコミュニティを生成するために、クラスタリング技術を再帰的に適用してよい。サンプリングおよびクラスタリングは、ランダムに生成された異なるサンプル化IBDネットワークに対して、様々な実行のために繰り返されてもよい。様々な実行においてサンプリングされたときに一貫して遺伝コミュニティに割り当てられたノードは、参照パネルサンプルとして分類されてもよい。コミュニティアサイメントエンジン２３０は、所定の閾値の観点で一貫性を測定してもよい。例えば、ノードがサンプリングされるたびに95％（または別の適切な閾値）の回数で同じコミュニティに分類されている場合、そのノードによって代表される個体に対応する遺伝データセットは、参照パネルサンプルとみなされてもよい。加えて、またはあるいは、コミュニティアサイメントエンジン２３０は、コミュニティの参照パネルとして、最も一貫して割り当てられたＮ個のノードを選択してもよい。
【００３８】
参照パネルサンプルを生成する他の方法も可能である。例えば、コンピューティングサーバー１３０は、一セットのサンプルを収集し、高品質の参照パネルサンプルが選択されるまで、サンプルを徐々にフィルタリングし、洗練させてもよい。
【００３９】
民族性推定エンジン２４５は、対象となる個体の遺伝データセットの祖先構成を推定する。使用される遺伝データセットは、遺伝子型データセットまたはハプロタイプデータセットであってもよい。例えば、民族性推定エンジン２４５は、対象となる個体のSNP遺伝子型またはハプロタイプに基づいて、先祖代々の起源（例えば、民族性）を推定する。アフリカ系、ヨーロッパ系、およびネイティブアメリカンに相当する3つの祖先集団の単純な例を取ると、混合されたユーザーは、[0.05, 0.65, 0.30]のような推定値で、ユーザーのゲノムがアフリカ系祖先に帰属する5％、ヨーロッパ系祖先に帰属する65％、およびネイティブアメリカン系祖先に帰属する30％であることを示すことで、3つの祖先集団すべてについてゼロではない、推定の民族性割合を有してもよい。民族性推定エンジン２４５は、民族組成推定値を生成し、推定された民族性を特定のユーザーと関連づけられたポインタとともにコンピューティングサーバー１３０のデータストアに格納する。
【００４０】
一実施形態では、民族性推定エンジン２４５は、対象となる遺伝データセットを複数のウィンドウ（例えば、約1,000個のウィンドウ）に分割する。各ウィンドウは、少数のSNPサイト（例えば、300個のSNPサイト）を含む。民族性推定エンジン２４５は、有向非巡回グラフモデルを用いて、対象となる遺伝データセットの民族組成を決定してもよい。有向非巡回グラフは、ウィンドウ間の隠れマルコフモデル（HMM）のトレリスを表してもよい。グラフは複数のレベルのシーケンスを含む。ウィンドウを表す各レベルは、複数のノードを含む。ノードは、ウィンドウに対する遺伝コミュニティ（例えば、民族）のラベルの、異なる可能性を表す。ノードは、１つ以上の民族ラベルでラベル付けされていてもよい。例えば、レベルは、SNPサイトのウィンドウが第１の民族に属する可能性を表す第１のラベルを有する第１のノードと、SNPサイトのウィンドウが第２の民族に属する可能性を表す第２のラベルを有する第２のノードとを含む。各レベルは、有向非巡回グラフを横断するための多くの可能なパスが存在するよう、複数のノードを含む。
【００４１】
有向非巡回グラフは、放出確率と遷移確率を含む。ノードに関連付けられた放出確率は、ウィンドウ内のSNPサイトの観測が与えられた場合に、そのウィンドウがそのノードをラベル付けした民族性に属する可能性を表す。民族性推定エンジン２４５は、対象となる遺伝データセットに対応するウィンドウ内のSNPサイトを、参照パネルサンプルストア２４０に格納された異なる遺伝コミュニティの様々な参照パネルサンプル内のウィンドウ内の対応するSNPサイトと比較することにより、放出確率を決定する。２つのノード間の遷移確率は、２つのレベルをまたいで１つのノードから別のノードへの遷移の可能性を表す。民族性推定エンジン２４５は、遷移確率および放出確率に基づいて、最も確率の高い経路または他の可能な経路の少なくとも９５％よりも確率が高い経路など、統計的に可能性の高い経路を決定する。パスを決定するために、ビタビアルゴリズムやフォワードバックワードアルゴリズムのような適切な動的計画法が用いられてもよい。パスが決定された後、民族性推定エンジン２４５は、決定されたパスに含まれるノードのラベル組成を決定することにより、対象遺伝データセットの民族組成を決定する。特許文献４には、民族性推定の例示的な実施形態が述べられている。
【００４２】
フロントエンドインターフェイス２５０は、コンピューティングサーバー１３０によって決定された様々な結果を表示してもよい。結果およびデータは、ユーザーと他の個体との間のIBD親和性、ユーザーのコミュニティ割り当て、ユーザーの民族性推定、表現型予測および評価、家系データ検索、家系図および血統書、親族プロフィール、および他の情報を含んでいてもよい。フロントエンドインターフェイス２５０は、各種情報やグラフィカル要素を表示するグラフィカルユーザーインターフェイス（GUI）であってもよい。フロントエンドインターフェイス２５０は、様々な形態をとってもよい。一実施形態においては、フロントエンドインターフェイス２５０は、コンピュータやスマートフォンなどの電子デバイスで表示可能なソフトウェアアプリケーションであってもよい。ソフトウェアアプリケーションは、コンピューティングサーバー１３０を制御するエンティティによって開発され、クライアントデバイス１１０にダウンロードされてインストールされてもよい。別の実施形態では、フロントエンドインターフェイス２５０は、ユーザーがウェブブラウザを介して家系図および遺伝子解析結果にアクセスすることを可能にするコンピューティングサーバー１３０のウェブページインターフェースの形態をとってもよい。さらに別の実施例では、フロントエンドインターフェイス２５０は、アプリケーションプログラムインターフェイス（API）を提供してもよい。
【００４３】
IBDネットワークの例
図３Ａおよび３Ｂは、一実施形態による例示的なアイデンティティーバイディセントネットワーク（IBDネットワーク）を示している。図３Ａを参照すると、例示的なIBDネットワークは、部分的に接続された無向グラフ３００であってもよい。グラフ３００は、複数のノード３０２を含む。各ノードは、遺伝データストア２１０に格納された遺伝データを有する個体の１つを表す。各ノード３０２は、個々の遺伝データセットに対応していてもよい。例えば、そのデータに基づいて、遺伝データセットは、特徴ベクトルとして表すことができる多数の特徴に変換されてもよい。ノード３０２は、ベクトルの座標に基づいて特徴ベクトルに対応してもよい。ノード３０２の一部は、エッジ３０４を介して接続される。IBDネットワークでは、２つ以上のノード３０２がエッジ３０４を介して接続されているが、すべてのノード３０２が必ずしも互いに直接接続されているわけではない。それゆえ、グラフ３００は、部分的に接続されたグラフであってもよい。例えば、特定のノード３０６は別のノード３０８に接続されているが、ノード３０６はノード３１０に直接接続されていない。グラフ３００は、例示のためだけのものである。実際のIBDネットワークグラフは、数万個のノード、または数百万個のノードを含み得る。
【００４４】
接続されたノードについては、エッジ３０４は重みに関連付けられており、その値は、２つのノードによって表される２つの個体の遺伝データセット間の親和性に由来する。例えば、２つの個体の遺伝データセット間の親和性は、２つの個体のフェージングハプロタイプデータセットを比較することによって決定される、２つの個体の共有IBD遺伝的セグメントの長さに対応するIBD親和性であってもよい。例えば、特定のエッジ３１２は、ノード３０８および３１０によって表される２つの個体がIBDに関連していることを表す。エッジ３１２に関連する重みは、２つの個体の共有IBD遺伝セグメントの長さに対応する。他の方法として、２つの遺伝的データセット間の親和性を比較することも可能である。
【００４５】
エッジ３０４は、異なる重みに関連付けられていてもよく、グラフ３００において異なる厚さを有するように示されている。例えば、エッジ３１４は、エッジ３１６よりも厚く、これはエッジ３１４によって接続された２つの個体が、エッジ３１６によって接続された２つの個体よりも高いIBD親和性を有することを示す。コンピューティングサーバー１３０は、親和性から重みの正確な値を導出してもよい。一実施形態においては、重みの値は、センチモルガンで測定されたIBD親和性であってもよい。別の実施形態では、重みの値は、IBD親和性からマッピングまたは変換されてもよい。例えば、コンピューティングサーバー１３０は、重みを０と１の間で正規化してもよい。
【００４６】
IBD親和性とエッジ重みとの間のマッピング関数は、可能な全IBDセグメント長のセットによって定義された関数領域を有する任意の連続関数または不連続関数であってもよい。一実施形態では、コンピューティングサーバー１３０は、(1)目標とする世代範囲を選択すること、(2)合理的に現実的なシミュレーションを使用して、その世代範囲内で共通の祖先を共有する個体のペア間の全IBD長の分布を経験的に評価すること、(3)選択した世代範囲に対応する共通の祖先を共有する家族関係から生じる総IBD長に高い重みが置かれるように親和性を定義すること、により、全IBDセグメント長をエッジ重みにマッピングする。これは、目標とする世代範囲内の共通祖先を共有する親族間のエッジをより重く重み付けする効果がある。例えば、0〜4世代前の世代範囲では、8つの減数分裂事象以下で隔てられた親族間の縁をより重視し、9つの減数分裂事象以下と、1つの減数分裂事象が親子関係に対応し、2つの減数分裂事象が兄弟関係や祖父母と子の関係に対応するような、より遠い親族間の縁をより軽視する。
【００４７】
一実施形態では、IBD-エッジ重みマッピング関数は、IBDネットワーク内のエッジの重みを定義するスケールパラメータα＝1.1およびβ＝10を有するベータ累積密度関数(CDF)（例えば、Probability(X ≦ x)（ここでxは個体の任意のペア間のIBD親和性である）に基づいて選択された。全IBD長からエッジの重みへのマッピングのための他の選択は、異なる特性を持つIBDネットワークを生成してもよい。例えば、より遠い家族関係を重視すると、異なる時間帯の人口イベントに起因する構造が明らかになり得る。
【００４８】
コミュニティアサイメントエンジン２３０などのコンピューティングシステム１３０のモジュールは、グラフ３００を表すデータを生成する。データは、キー-値のペア形式、ベクトル形式、行列形式、テンソル形式、またはそれらの１つ以上の組み合わせを含む任意の適切な形式であってもよい。例えば、ノードは、ノードによって表される個体を識別するキーとしての識別子と、遺伝データセットから生成された特徴ベクトルである値とを関連付けてもよい。Ｎ個の個体については、エッジを表すデータは、ノードｉとノードｊを結ぶエッジに対するセル（ｉ，ｊ）の重み値を記録するＮ×Ｎ行列形式であってもよい。ＩＢＤに関連していない（または閾値以下のIBDセグメント長を有する）２つの個体については、セル（ｉ，ｊ）は、２つの個体を表す２つのノードを結ぶエッジがないことを示すために、値０またはｎｉｌを有してもよい。
【００４９】
遺伝コミュニティ推論
図３Ｂは、一実施形態による、IBDネットワークおよびコミュニティ推論におけるアプローチ例を示している。コンピューティングシステム１３０は、グラフ３００内のノード３０２を、ノード３０２を接続するエッジ３０４の重みに基づいて複数のクラスターに分割する。例えば、図示のために、グラフ３００は、２本の破線で囲まれた２つのクラスター３２０、３３０に分割されてもよい。決定された各クラスターは、民族などの遺伝コミュニティを表してもよい。
【００５０】
IBDネットワークをクラスター化するためには様々なアルゴリズムが用いられてもよい。例としては、各サブセット内のエッジの密度が予想よりも高いネットワークの接続されたサブセットを識別するために用いられてもよい機械学習における任意の適切な教師なしアルゴリズムが挙げられる。以下に説明するのは、IBDネットワークにおいてクラスターが識別されることができる、ふさわしい方法の１つである。代替的なネットワーククラスタリングアルゴリズムの例としては、スペクトルグラフクラスタリング法が挙げられる。他の教師なし、または半教師ありのコミュニティ検出アルゴリズム、例えば、ラベル伝搬アルゴリズム、連結成分アルゴリズム、三角形カウンティング係数アルゴリズム、平衡三角形アルゴリズムなども用いられてよい。
【００５１】
一実施形態では、コンピューティングサーバー１３０は、モジュラリティに基づくコミュニティ検出アルゴリズムであるマルチレベルルーバン法の再帰的な適用を介してコミュニティを識別する。他の実施形態では、コミュニティは、別のモジュラリティを基にしたコミュニティ検出アルゴリズムの再帰的な適用を介して識別されてもよい。モジュラリティを基にしたコミュニティ検出アルゴリズムの例としては、Fast-Greedyアルゴリズム、固有ベクトルベースのアルゴリズム、半正定値プログラム（SDP）を基にしたアルゴリズムなどが挙げられる。
【００５２】
モジュラリティに基づくコミュニティ検出アルゴリズムにおいて、コンピューティングサーバー１３０は、グラフ３００の高いモジュラリティのパーティションを識別する。モジュラリティは、各パーティション内のノードを接続するエッジの重みに基づいて、パーティションがどのように定義されているかを測定する因子である。各々が重みを有するエッジＭを介して互いに接続されたＮ個のノードを含むIBDネットワークＳにおいて、モジュラリティは、あるパーティション内のノードと別のパーティション内のノードとを接続するエッジの重みに対して、同じパーティションに分類された２つのノードを接続するエッジの重みを測定する任意の好適な方法で定義されてもよい。例えば，ある事例では，ネットワーク分割のモジュラリティ値Qは次のように定義される。
Q=ΣkΣ(i,j)∈Skaij-(didj)/2m (1)
ここで、kはコミュニティインデックス、Skはコミュニティkに割り当てられた全てのノード間のエッジのセット、aijはエッジ（ｉ，ｊ）の重み、diはノードiの「度数」であり、ノードｉを接続するエッジの全てのエッジ重みの総和と定義され、ｍは全ての「度数」の総和である。
【００５３】
一般に、モジュラリティは、同じパーティションに分類される２つのノードを結ぶエッジの重みとともに増加し、１つのパーティション内のノードを別のパーティション内のノードに結ぶエッジの重みとともに減少する値を有し得る。例えば、図３Ｂでは、破線で定義されたような候補となるパーティション３２０は、候補となる遺伝コミュニティを表すものであり、うまく定義されたパーティションを表し得る。それは、エッジの大部分が、パーティション３２０に分類されたノードに接続されているからである。エッジ３２２やその近傍のエッジのように、パーティション３２０内にあるノードとパーティション３２０外にある別のノードとを接続しているエッジは、ごくわずかである。また、エッジ３２２を含むそれらのエッジは、重みの値が低いことを意味する細い線である。よって、式(1)または他の適当なモジュラリティの定義に基づいて、パーティション３２０は高いモジュラリティの値を有する。対照的に、別の候補となる遺伝コミュニティを表す可能性があるパーティション３４０は、低いモジュラリティの値を有しており、これは候補となる遺伝コミュニティもまた貧弱な定義であることを示している。これは、パーティション３４０内のノードとパーティション３４０外の別のノードとを結ぶエッジが多く存在するためである。例えば、ノード３４２は、次数が５（５個のエッジ）であるが、すべてのエッジは、パーティション３４０の外側にある別のノードに接続されている。コンピューティングサーバー１３０は、グラフ３００内のパーティションを調整するアルゴリズムを用いて、モジュラリティの値を増加させる。アルゴリズムは、IBDネットワークに関連付けられたモジュラリティを増加させるか、またはヒューリスティックに最大化する。調整されたパーティションは、IBDネットワークの最終的なクラスターであってもよい。アルゴリズムは、所定の反復回数（例えば、エポック数）を終了したとき、またはすべてのパーティションの全モジュラリティ値がそれ以上増加しない（例えば、収束する）まで停止してもよい。コミュニティ検出アルゴリズムに関連する計算時間は、エッジ数Ｍ（例えば、複雑さ＝Ｏ（Ｍ））とともに線形に増大してもよい。
【００５４】
コミュニティ検出アルゴリズムは、Ｎ個のノードからなるネットワークＳをＣ個のコミュニティに分割する。ネットワークのコミュニティへの分割は、（Ａ1，Ａ2，Ａ3... ，ＡC)と表示される。コミュニティ検出アルゴリズムに続き、コミュニティ（Ａ1，Ａ2，Ａ3... ，ＡC)は、それぞれが少なくとも所定の閾値ノード数ｔを含む場合、「有効」とラベル付けされる。一実施形態では、閾値ノード数未満のコミュニティAiは、有効なコミュニティとはみなされず（すなわち、「無効な」コミュニティ）、したがって、コミュニティ検出分析およびモデル学習の後続のステップから省略される（その構成ノードは、コミュニティとしてラベル付けされることなく、単独で放置されてもよい）。一実施形態では、ノードの閾値数Ｔは1,000である。しかし、他の実施形態では、閾値数は、０より大きい任意の整数のノード数であり、有効とラベル付けされたコミュニティのセットは、（Ａ’1，Ａ’2，Ａ’3... ，Ａ’C’)で示され、Ｃ'は、Ｃ以下である。
【００５５】
コミュニティの最小サイズに対するこの閾値のカットオフは、検出されたコミュニティが歴史的または地理的に重要なグループとして解釈されるのに十分な数のノードを含むことを確実にするのに有用となり得る。もし、コミュニティが閾値のノード数tよりも少ない場合、追加のコミュニティ検出アルゴリズムを適用して生成された追加のサブコミュニティは、潜在的にデータのオーバーフィットまたは過剰分析の結果である可能性が高い。これは、その分野の専門家が認識するような類似体を持っていないサブ集団を示唆し得る。ノードの閾値数は、システムの正確な実装およびIBDネットワーク３００内のサンプル数に応じて、1,000〜10,000の間のどこにも取り得る。
【００５６】
一実施形態においては、コミュニティ検出アルゴリズムは、再帰的に適用されてもよい。コミュニティ検出の第１ラウンドを適用した後、コンピューティングサーバー１３０は、サブクラスターを生成するために、識別されたクラスターに再びコミュニティ検出アルゴリズムを適用し続けてもよい。コンピューティングサーバー１３０は、サブクラスターのすべてが十分なメンバーを持たない（閾値ノード数よりも少ない）まで、このプロセスを繰り返してもよい。コミュニティ検出アルゴリズムの繰り返しは、図７Ａ〜図９に関連してさらに詳細に論じられる階層的コミュニティ検出アプローチと呼ばれてもよい。
【００５７】
一実施形態では、遺伝コミュニティおよびサブコミュニティが特定された後、コンピューティングサーバー１３０は、個体に関連付けられた家系データに基づいてコミュニティに注釈を付けてもよい。例えば、あるコミュニティについては、ノード３０２によって表される個体の少なくとも一部は、コンピューティングサーバー１３０の家系データストア２０５に格納されたプロフィールデータ、地理データ、および先祖データなどの家系データを有する。また、コンピューティングサーバー１３０は、民族性推定エンジン２４５を用いて、コミュニティメンバーの遺伝データセットを分析してもよい。様々な情報源から決定された民族性および地理的起源データに基づいて、コンピューティングサーバー１３０は、コミュニティのメンバーが共通して民族性および／または地理的起源を共有していると決定してもよい。コンピューティングサーバー１３０は、コミュニティに民族性および／または地理的起源に注釈をつけてもよい。
【００５８】
IBDネットワークのフィルタリング
図４は、一実施形態による、IBDネットワークをフィルタリングする例示的なプロセスを描いたフローチャートである。図５は、一実施形態による、フィルタリングされたグラフの例を示している。図４を参照し、コンピューティングサーバー１３０は、複数の個体に対応する複数の遺伝データセットを引き出す４１０。遺伝データセットは、個体の遺伝データセットまたはフェージングされたハプロタイプデータセットであってもよい。様々な数の遺伝データセットが引き出されてもよい。ある実施形態では、コンピューティングサーバー１３０は、1,000以上の遺伝データセットを取得してもよい。別の実施形態では、コンピューティングサーバー１３０は、10,000以上の遺伝データセットを取得してもよい。さらに別の実施形態では、コンピューティングサーバー１３０は、数十万以上、または数百万以上の遺伝データセットを取得してもよい。与えられた個体のペアの共有IBD遺伝セグメントの長さに基づいて、所定の個体のペアの遺伝データセット間の親和性を表すIBD親和性も決定されてもよいし、コンピューティングサーバー１３０によって予め決定されて記憶されていてもよい。
【００５９】
コンピューティングサーバー１３０は、フルグラフを表すデータ４２０を生成する。フルグラフは、IBDネットワークであってもよい。フルグラフは複数のノードを含んでもよい。各ノードは、個体の１つを表す。２つ以上のノードは、エッジを介して接続されている。各エッジは、２つのノードを接続し、２つのノードによって表される２つの個体の遺伝データセット間の親和性に由来する重みに関連付けられる。グラフがIBDネットワークである場合、親和性はIBD親和性であってもよい。もし、グラフが、２つの個体の遺伝データセット間の類似性を測定するために他の方法を使用する場合、重みを生成するために用いられる親和性を表すため。他の種類の測定値が使用されてもよい。フルグラフは、まだフィルタリングされていないグラフを表してもよい。フルグラフは、コンピューティングサーバー１３０が、グラフを表すデータを生成するために利用可能な全ての遺伝データセットを用いる必要はない。
【００６０】
コンピューティングサーバー１３０は、エッジまたはノードの１つ以上の特徴に基づいて、フルグラフを表すデータをフィルタリングする４３０。フィルタリングされたデータは、ノードのサブセットを表す。例えば、図５は、図３Ａに示されたフルグラフ３００からフィルタリングされ得る、フィルタリングされたグラフ５００を示している。ノード５１０のような実線のノードは、選択されたノードである。ノード５２０のような破線のノードは、非選択ノードである。フィルタリングは、エッジに関連付けられた１つ以上の特徴および／またはノードに関連付けられた１つ以上の特徴に基づいてもよい。
【００６１】
フルグラフをフィルタリングするために用いられる特徴は、様々なタイプのものであってよい。特徴は、グラフに直接含まれているか使用されているデータであってもよいし、ノードやエッジに関連しているが、グラフには使用されていないデータであってもよい。グラフに直接含まれる特徴は、２つの遺伝データセット間の親和性の特徴であってもよい。例えば、エッジの強さ（例えば、重みの値）は、フルグラフをフィルタリングするために用いられてもよい。対照的に、グラフに使用されない特徴は、エッジまたはノードが表すものに関連する物または人の他の特徴であってもよい。例えば、エッジは２人の個体間の接続または関係を表すので、エッジの特徴は、エッジによって接続された２人の個体によって共通に共有される人または物の特徴であってもよい。一実施形態において、例示的な特徴は、ノードがエッジによって接続されている２つの個体によって共通で共有されている先祖の特徴であってもよい。祖先が２つの個体によって共有されているので、祖先の特徴は、２つの個体間の接続を表すエッジの特徴であってもよい。先祖の特徴の例としては、先祖の誕生年が挙げられる。また、２人の個体が複数の先祖を共有している場合には、平均出生年を用いてもよい。平均出生年は、共通祖先が１人しかいない場合の出生年である。コンピューティングサーバー１３０は、共通祖先の出生年の時間枠（例えば、1800〜1850）に基づいて、フルグラフを表すデータをフィルタリングしてもよい。また、共通祖先の地理的起源、共通祖先の民族性、共通祖先の苗字などを含む他の祖先の特徴も、グラフをフィルタリングするために用いられてもよい。
【００６２】
例示的な特徴は、ノードの特徴を含んでもよい。ノードは個体を表すので、ノードの特徴は個体の特徴であってもよい。個体の特徴の例としては、個体の民族構成、個体の表現型（例えば、身体的特徴、疾患）、個体が生まれた地理的地域などが挙げられる。一実施形態では、ノードによって表される個体の遺伝データセットは、対象となる民族に遺伝する個体の遺伝セグメントの長さが閾値を超えていることを示してもよい（例えば、遺伝データセット全体の２０％が対象となる民族に帰属することを示す）。コンピューティングサーバー１３０は、選択されたノードが少なくとも２０％の対象となる民族に帰属する遺伝データを有することを要求することにより、フルグラフを表すデータをフィルタリングしてもよい。
【００６３】
コンピューティングサーバー１３０は、フィルタリングされたグラフを表すノードのサブセットを選択する際に、フルグラフを表すデータをフィルタリングするための１つ以上の特徴を用いてもよい。また、コンピューティングサーバー１３０は、フルグラフをフィルタリングするために、１つ以上のエッジ特徴および／または１つ以上のノード特徴を組み合わせてもよい。
【００６４】
コンピューティングサーバー１３０は、フィルタリングされたグラフのノードのサブセットを、サブセット内のノードを接続するエッジの重みに基づいて複数のクラスターに分割する４４０。各クラスターは、遺伝コミュニティを表してもよい。例えば、コンピューティングサーバー１３０は、上述したコミュニティ検出アルゴリズムを用いて、フィルタリングされたグラフ内のサブセットのノードを複数のクラスターに分割する。一実施形態では、コンピューティングサーバー１３０は、フィルタリングされたグラフ内に複数のパーティションを定義する。各パーティションは、候補となる遺伝コミュニティを表してもよい。最初は、定義されたパーティションは、候補となるコミュニティのメンバーが十分な接続または類似性を共有していないかもしれないことを意味する亜最適であってもよい。コンピューティングサーバー１３０は、パーティションの因子（例えば、モジュラリティ）を決定する。因子は、同じパーティションに分類される２つのノードを接続するエッジの重みが増加するほど増加し、一方のパーティションのノードを別のパーティションのノードに接続するエッジの重みが減少するほど減少する値を有する。コンピューティングサーバー１３０は、因子の値が増加するようにパーティションの境界を調整する。場合によっては、コンピューティングサーバー１３０は、因子を測定し、パーティションを調整するために多重の反復を使用する。最終的に調整されたパーティションは、遺伝コミュニティを表すクラスターであってもよい。
【００６５】
コミュニティ検出アルゴリズムが適用される前にフルグラフをフィルタリングし、フィルタリングされたグラフを生成することにより、コンピューティングサーバー１３０は、フルグラフを使用して発見できないかもしれない追加のコミュニティを発見することができる。例えば、図５を参照すると、フィルタリングされたグラフ５００は、コンピューティングサーバー１３０が、コミュニティ検出アルゴリズムを使用して、フルグラフでは分離できない２つのコミュニティ５３０、５４０を識別し、分離することを可能にする。図３Ｂを参照すると、２つのコミュニティ５３０、５４０は、クラスター３２０に属しているが、フルグラフ３００においては分離できない。フィルタリングアプローチを用いると、コンピューティングサーバー１３０は、フルグラフを使用して、以前には識別できなかった集団を識別することができる。一実施形態では、コンピューティングサーバー１３０は、グラフ内のノードによって表される個体の共通祖先の出生年に基づいて、フルグラフをフィルタリングする。コンピューティングサーバー１３０は、フィルタリングされたグラフの中で、ミシガン州、ウィスコンシン州、ミネソタ州、アイオワ州、テキサス州、ユタ州などの米国の異なる州の人口を表すクラスターを識別する。より最近の関係を含めることにより、グラフ内のすべてのエッジを使用した場合、より古い関係がより最近の構造をカバーし得るため、最近の人口構造を特定することができる。同様のアプローチを用いて、オーストラリアと南アフリカの人口を表すコミュニティもまた、様々なフィルタリングされたグラフによって識別される。
【００６６】
図６は、一実施形態による、２人の個体の共通祖先の出生年を時間枠に分類する例示的なプロセスを示すブロック図である。IBDネットワーク３００のようなグラフでは、コンピューティングサーバー１３０は、グラフ内のエッジに対応する全ての共通祖先の出生年に関するデータを保有していない可能性がある。例えば、コンピューティングサーバー１３０は、２人の個体が近親のIBDであると判断しても、コンピューティングサーバー１３０にとって共通祖先が不明であるため、出生年が不明となる場合がある。しかし、IBDセグメントの長さは、２人の個体が何世代前に関連しているかと相関し得るので、モデル（例えば、分類器）は、共通祖先の誕生年を予測する、または共通の祖先を時間枠（例えば、1700〜1800、1800〜1900）に割り当てるようにトレーニングされてもよい。未知の祖先または出生年が不明な祖先に対応するエッジについては、共有のIBD遺伝セグメントの長さを入力として取るモデルを使用して、２人の個体の共有のIBD遺伝セグメントの長さから出生年を推定してもよい。出生年が推定または時間枠に分類された後、コンピューティングサーバー１３０は、フルグラフをフィルタリングし、コミュニティ検出アルゴリズムを実行してもよい。
【００６７】
コンピューティングサーバー１３０は、その家系データストア２０５からのデータを用いて、ラベル付けされたトレーニングセットを生成してもよい。例えば、コンピューティングサーバー１３０は、個体Ａ６０２および個体Ｂ６０４の遺伝データセットを遺伝データストア２１０から取得してもよい。コンピューティングサーバー１３０のIBD推定エンジン２２５は、遺伝データセットに基づいて、個体Ａと個体ＢがIBD共有の長さで関連しているIBDであると決定してよい。コンピューティングサーバー１３０は、個体ＡおよびＢの家系図のデータなどの家系データを引き出す。個体ＡおよびＢは、別々の家系図を持っていてもよく、彼らが関連IBDであることを知らない可能性もある。家系図データから、そして潜在的には他の家系データの検証も含めて、コンピューティングサーバー１３０は、個体のペアが共通祖先６０６を共有していると判断する。共通祖先６０６は、コンピューティングサーバー１３０で利用可能な出生年データを有する。例えば、個体ＡまたはＢの一方が出生年を入力してもよいし、コンピューティングサーバー１３０は、出生記録証明書データのような公的な記録源から共通祖先６０６の出生年を見つけることができる。コンピューティングサーバー１３０は、共通祖先の出生年６１２とIBDセグメント長６１４を２つの特徴量として含むトレーニングセット６１０を生成し、このトレーニングセット６１０には、共通祖先出生年６１２とIBDセグメント長６１４が含まれる。共通祖先出生年６１２は、トレーニングセット６１０のラベルとして使用されてもよい。コンピューティングサーバー１３０は、そのデータストア内で、IBD関連であり、かつ出生年が既知である共通祖先を有する個体の、より多くのペアを繰り返し識別してもよい。複数のトレーニングセットが生成されてもよい。
【００６８】
コンピューティングサーバー１３０は、トレーニングセット６１０を用いてモデル６２０をトレーニングする。モデル６２０は、推定された出生年を可能な時間枠のいずれかに分類する分類器であってもよいし、共通祖先の出生年を予測する回帰器であってもよい。例えば、分類器としては、物流回帰分類器、ランダムフォレスト分類器、サポートベクターマシン（SVM）、ニューラルネットワーク等が用いられ得る。分類器の目的となる関数は、トレーニングセットを正しい時間枠に分類する際の誤差であってもよい。分類器のトレーニングにおいて、コンピューティングサーバー１３０は、座標降下または確率的座標降下（SGD）などの技術を用いて、誤差を低減または最小化するようにモデルの重みを調整する。一実施形態では、祖先の出生年の時間枠を予測するためにIBDセグメント長６１４を使用する物流回帰分類器が使用されてもよい。ランダムフォレストやSVMなどの非線形モデルも使用されてよい。いくつかの実施形態では、コンピューティングサーバー１３０は、出生年を予測するために追加の特徴を使用してもよい。例えば、様々な家系データも、共通祖先出生年の時間枠を予測するのに役立つかもしれない。コンピューティングサーバー１３０は、時間枠を予測するために、IBDセグメント長６１４および他の特徴を受信するニューラルネットワークをトレーニングしてもよい。
【００６９】
モデル６２０が十分にトレーニングされた後、トレーニングモデル６３０は、共通祖先出生年の時間枠６３６を予測するために使用されてもよい。IBDネットワークにおけるエッジの重みは、IBDセグメント長から導出されるので、IBDセグメント長は、与えられたエッジについて既知である。与えられたエッジについては、時間枠６３６を生成するために、IBDセグメント長６３４を含む入力データセット６３２がトレーニングされたモデルに入力されてもよい。予測された時間枠がIBDネットワークのフルグラフ内のエッジについて生成された後、コンピューティングサーバー１３０は、予測された時間枠に基づいてフルグラフをフィルタリングし、対象となる時間枠内に生まれたと推定された共通祖先を表すエッジを選択する。次に、コンピューティングサーバー１３０は、コミュニティ検出アルゴリズムを適用して、対象となる時間枠に関する遺伝コミュニティを発見する。
【００７０】
例えば、1700年代に存在したコネチカット州の人口は1800年代に西へ移動し、他の人口と混合した。既存の方法では、すべてのマッチが使用された場合、この人口移動に対応する構造を特定することはできなかった。対照的に、1700年代に生まれた共通祖先に対応するフィルタリングされたグラフを生成することにより、コンピューティングサーバー１３０は、ニューヨークへの移動に関連するその時期のコネチカット州の人口構造を特定することができる別の例としては、オーストラリアが挙げられる。コンピューティングサーバー１３０は、フルグラフを用いてオーストラリアのコミュニティを見つけることができないことがあり得る。しかし、1800年代のそれらのエッジのみを使用することにより、コンピューティングサーバー１３０は、19世紀の交配パターンに起因するオーストラリアの人口構造を特定する。
【００７１】
機械学習モデルを用いる代わりに、２つの個体間の共通祖先の時間を見つけることは、集団遺伝モデルを用いて近似することができる。例えば、IBDセグメント長の統計分布を生成し、共通祖先の世代を予測することができる。世代は、集団遺伝モデルが利用可能な場合、年にマッピングすることができる。
【００７２】
共通祖先の出生年の時間枠などのエッジ特徴を用いてフルグラフをフィルタリングすることに代わり、またはそれに加え、コンピューティングサーバー１３０は、ノードによって表される個体の民族性構成などのノード特徴を用いてフルグラフをフィルタリングしてもよい。このアプローチにより、コンピューティングサーバー１３０のデータストアに過剰に表現されている可能性のある他のグループのノイズを除去することができる。場合によっては、コンピューティングサーバー１３０は、特定の地域の顧客の間では、比較的大衆的があるが、別の地域では大衆的ではない場合がある。このように、構築されたIBDネットワークに偏りが生じる場合があり、いくつかの母集団構造が他の母集団構造よりも強い場合がある。場合によっては、これにより、特定の大衆的でない母集団の構造を発見することが困難になる。コンピューティングサーバー１３０は、関心のある特定の民族性の個体のみをフィルタリングしてもよい。例えば、フルグラフがアジア系の個体を含むようにフィルタリングされると、アジアにおけるより良く、より洗練された集団構造が発見され得る。このアプローチは、混合された集団のための、より洗練されたコミュニティ発見をもたらす。
【００７３】
一実施形態では、コンピューティングサーバー１３０は、ノードの選択されたサブセットが、対象となる民族起源に帰属する遺伝データの少なくとも一定の割合（例えば、20%）を含むことを要求することにより、フルグラフのノードをフィルタリングしてもよい。コンピューティングサーバー１３０は、個体の遺伝データセットを対象となる民族由来の１つ以上の参照パネルサンプルと比較することにより、対象となる民族由来に遺伝する個体の遺伝セグメント長を決定してもよい。例えば、コンピューティングサーバー１３０は、個体の民族構成を決定するために、民族推定エンジン２４５を使用してもよい。混合された個体の場合、個体を表すノードは、複数のフィルタリングされたグラフで選択されてもよい。例えば、フルグラフを表すデータをフィルタリングして第１のフィルタリングされたグラフを生成することは、個体の民族組成において提示された第１のターゲット民族に基づいてもよい。さらに、第２のフィルタリングされたグラフを生成するためにフルグラフを表すデータをフィルタリングすることは、個体の民族組成において提示された第２のターゲットの民族性に基づいてもよい。例えば、フィルタリングの基準は、各フィルタリングされたグラフが、少なくとも20%の対象となる民族性を有する個体を含むことを要求してもよい。その結果、混合された個体を表すノードが、第１のフィルタリングされたグラフと第２のフィルタリングされたグラフの両方に存在してもよい。
【００７４】
マルチパス階層コミュニティ検出
図７Ａ〜図９は、一実施形態による、例示的なマルチパス階層コミュニティ検出プロセスを示している。図７Ａは、シングルパスの階層コミュニティ検出プロセスのための樹形図７００である。樹形図７００は、複数の枝と端葉を含み、これらはそれぞれ、「1」、「2.1」、「5.2.5」、「6.3.4」などのような数値識別子によって示される。枝は、葉に到達するための経路を表す。葉は、コミュニティ検出処理におけるIBDネットワークなどのグラフにおけるクラスターに対応するコミュニティまたはサブコミュニティを表す。
【００７５】
階層コミュニティ検出プロセスでは、コンピューティングサーバー１３０は、コミュニティ検出アルゴリズム（例えば、ルーヴァン法）をグラフ（フルグラフまたはフィルタリングされたグラフ）に適用し、グラフをコミュニティのセットを表すクラスターに分割する。コミュニティのセットが決定された後、コンピューティングサーバー１３０は、クラスター内のサブクラスターを特定するために、各クラスターに再びコミュニティ検出アルゴリズムを適用する。各サブクラスターは、さらに定義された遺伝コミュニティを表してもよい。コミュニティの初期セットとサブコミュニティを区別するために、コミュニティの初期セットは「レベル１」コミュニティと呼ばれてもよく、サブコミュニティは「レベル２」コミュニティと呼ばれてもよい。複数のレベルのコミュニティは、クラスターの階層的なセットとして見てもよい。
【００７６】
レベル１の各コミュニティＡi'（ｉ＝１，２，...，Ｃ'）についてサブコミュニティを特定するために、コンピューティングサーバー１３０は、コミュニティＡi'（ｉ＝１，２，３,...，Ｃ'）のセット内の各コミュニティＡi'についてのサブグラフｇiを表すデータを生成する。サブグラフｇiは、コミュニティＡi'に割り当てられたノードｎのサブセットとエッジｍのサブセットとによって定義され、ｉとｊの両方がコミュニティAi’に割り当てられている場合に（ｉ，ｊ）がサブセットに含まれる。
【００７７】
コンピューティングサーバー１３０は、コミュニティＡi'に関連付けられたサブグラフｇｉにクラスタリングアルゴリズム（例えば、モジュール化ベースのクラスタリング）を適用する。例えば、レベル１のコミュニティＡ1'がサブグラフｇ1に関連付けられている場合、そのサブグラフｇ1にクラスタリングアルゴリズムを適用する。クラスタリングアルゴリズムを、ｉ＝１，２，...，Ｃ'の各サブグラフｇｉに適用した後、結果は、サブコミュニティのセット（Ｂ1，Ｂ2，...，ＢD）となり、ここで、Ｄは全てのサブグラフで識別されたサブコミュニティの総数である。一実施形態では、以前に指定されたサイズを超える「有効な」コミュニティのみが保持され（これは、レベル１コミュニティを決定するために使用される（第１の）閾値ｔとは異なる（第２の）閾値であってもよい）、その結果、レベル２コミュニティの最終セットであるサブコミュニティ（Ｂ'1，Ｂ'2，...Ｂ'D'）が得られ、その中でＤ'はＤ以下である。
【００７８】
上述した処理は、少なくとも１つのコミュニティが上述の閾値ノード数Ｔよりも大きいノードを有する限り、後続のレベルのコミュニティに対して繰り返されてもよい。例えば、レベル３のコミュニティは、再度細分化され、レベル２のコミュニティＢiごとにサブグラフｇiを生成し、各サブグラフｇiにコミュニティ検出アルゴリズムを適用してもよい。
【００７９】
本説明に続いて、以下に階層型コミュニティ検出アルゴリズムのためのコンピューティングサーバー１３０の例示的な擬似コードを示す。
【００８０】
2021530026.tif 000003
【００８１】
一実施形態においては、上述の例示的な擬似コードによって定義された手順は、接続されたノードのグループを再帰的に断片化または細分化することにより、コミュニティの階層をもたらす。上述の疑似コードによって例示されたアルゴリズムは、コミュニティによって定義されたサブネットワークのサイズが、1,000ノードのようなユーザー指定の変数であり得るノードの閾値数Ｎよりも少ないノードを含む場合に、さらなる細分化を自動的に停止する。さらに、サブグラフを作成するためには、サブネットワークの安定性が閾値Ｍを超える必要がある。
【００８２】
シングルパス階層コミュニティ検出アプローチでは、コミュニティ検出の各レベルのノードは、単一のクラスターに割り当てられ、単一のクラスターのみに割り当てられる。したがって、シングルパスアプローチでは、個体を表すノードは、葉までの単一のパスによってのみ樹形図７００をトラバースすることができる。例えば、図７Ａは、葉に到達する例示的なパスを示している。レベル１（例えば、コミュニティ検出アルゴリズムの第１ラウンド）では、ノードは第６のクラスターに割り当てられる。シングルパスアプローチでは、ノードは、第６クラスターと別のクラスターに同時に割り当てられない。したがって、パスは、第６クラスターを表す分岐を取るが、他のクラスターは取らない。レベル２（例えば、コミュニティ検出アルゴリズムの第２ラウンド）では、ノードは、第６クラスターの第３サブクラスター（６．３）に割り当てられる。レベル３（例えば、コミュニティ検出アルゴリズムの第３ラウンド）では、ノードは、葉６．３．１に到達し、サブクラスター６．３の第１サブクラスターに割り当てられる。
【００８３】
図７Ｂは、一実施形態による、マルチパスコミュニティ検出プロセスのための樹形図７００を示している。このマルチパスアプローチでは、コミュニティ検出の各レベルにおけるグラフ内のノードは、マルチクラスターに割り当てられることが許容される。したがって、レベル１では、葉６．３．１に到達するパスに加え、ノードは、第３クラスターおよび第４クラスターにも割り当てられる。また、レベル２では、ノードは第４クラスターの第１および第４サブクラスターに同時に割り当てられる。コミュニティ検出アルゴリズムのマルチラウンドの後、コンピューティングサーバー１３０は、ノードをコミュニティ６．３.１、３．１、４．１、および４．４.５に割り当てる。言い換えれば、ノードは、異なるコミュニティおよびサブコミュニティに到達するためにマルチパスを取ることができる。一実施形態では、各レベルにおいて、コンピューティングサーバー１３０は、まずクラスタリングアルゴリズムを使用し、グラフ内のノードをマルチクラスターに分割し、対象ノードをシングルクラスターに割り当ててもよい。ルーヴァン法のような方法は、ノードを１つのクラスターにのみ割り当ててもよいので、対象ノードは、シングルクラスターにのみ割り当てられる。次に、コンピューティングサーバー１３０は、１つ以上の基準に基づいて、対象となるノードを付加的なクラスターに追加してもよい。例えば、基準は、上述したようなフィルタリング基準に基づいてもよい。別の実施形態では、基準は、以下でさらに詳細に論じられる安定性の因子に基づいている。
【００８４】
図８は、一実施形態による、マルチパスコミュニティ検出を実行するための例示的なプロセスを描いたフローチャートである。このプロセスは、混合された個体を１つ以上の遺伝コミュニティに分類するために用いることができる。コンピューティングサーバー１３０は、複数の個体に対応する複数の遺伝データセットを引き出す８１０。個体のうちの少なくとも１つは、混合された個体である。コンピューティングサーバー１３０は、部分的に接続された無向グラフであってもよいグラフを表すデータを生成８２０する。本開示で議論される他のグラフと同様に、このグラフは、複数のノードを含んでもよい。各ノードは、個体の１つを表す。２つ以上のノードは、エッジを介して接続されている。各エッジは、２つのノードを接続し、２つのノードによって表される２つの個体の遺伝データセット間の親和性に由来する重みに関連付けられる。複数のノードは、混合された個体を表す、対象となるノードを含む。
【００８５】
コンピューティングサーバー１３０は、ノードを接続するエッジの重みに基づいて、グラフ内のノードを複数のクラスターに分割８３０するために、コミュニティ検出アルゴリズムを適用してもよい。複数のクラスターは、複数の遺伝コミュニティを表す。コンピューティングサーバー１３０は、１つ以上の異なる遺伝コミュニティを表す１つ以上のクラスター内に対象となるノードを含む８４０。一実施形態では、対象ノードは、２つ以上の遺伝コミュニティに含まれる。例えば、コンピューティングサーバー１３０は、最初にコミュニティ検出アルゴリズムを用いて、１つのクラスターの対象となるノードを割り当てることができる。次に、コンピューティングサーバー１３０は、安定性の因子などの１つ以上の基準に基づいて、対象となるノードを付加的なクラスターに追加する。
【００８６】
対象ノードが含まれるクラスターの少なくとも１つについて、コンピューティングサーバー１３０は、クラスターを複数のサブクラスターに分割８５０する。例えば、コンピューティングサーバー１３０は、グラフ、クラスター、または任意のサブクラスターをさらに定義されたサブクラスターに分割する際に、ステップ８３０および８５０における同じコミュニティ検出アルゴリズムを適用してもよい。コンピューティングサーバー１３０は、対象となるノードをサブクラスターの１つに分類してもよい。対象となるノードは、混合された個体が、１つ以上の民族起源の１つ以上の異なる遺伝サブコミュニティに分類されていることを表す、１つ以上の異なるサブクラスターに分類される。矢印８６０で示されるように、コンピューティングサーバー１３０は、ステップ８４０および８５０を繰り返して階層アプローチを用い、異なるパスの下で対象となるノードをさらに多くのサブクラスターに割り当てることができる。
【００８７】
階層コミュニティ検出プロセスの特定のレベルにおいて、対象となるノードを付加的なクラスターに追加すべきかどうかは、対象となるノードとクラスターとの間の関連性がどの程度安定しているかを評価するための対象となるノードの安定性分析に依存してもよい。例えば、図８のステップ８２０に対応して、コンピューティングサーバー１３０は、対象となるノードが閾値を超える特定のクラスターに関する安定性を有するかどうかを決定する。コンピューティングサーバー１３０は、閾値を超える安定性に応答して、特定のクラスターに対象となるノードを含める。
【００８８】
安定性は、対象となるノードと対象となるクラスターとの間の接続を測定する安定性の因子の形態を取ってもよい。コンピューティングサーバー１３０は、ステップ８３０を所定のグラフに対して実行し、対象となるクラスターを含むクラスターのセットを生成してもよい。同じグラフに対し、コンピューティングサーバー１３０は、グラフの複数のノードからノードのサブセットをランダムにサンプリングする。ノードのサブセットは、サンプリングされたグラフを表し、多くの場合、与えられたグラフのノードの約一定の割合（例えば、60〜80%）を含んでいる。コンピューティングサーバー１３０は、サンプリングプロセスを繰り返し、複数のノードのサブセットを生成する。異なるサンプリングがされたグラフを表す、様々なサブセットが生成される。コンピューティングサーバー１３０は、サンプリングされたグラフの各々を複数のクラスターに分割する。分割された結果は、対象となるクラスターを含んでもよい。対象となるクラスターは、各サンプルされたグラフについて完全に同一ではなくてもよく、ランダムにサンプルされたグラフにコミュニティ検出アルゴリズムを適用すると、コミュニティの異なる数および分割が生成される可能性があるため、サンプルされていないグラフを用いて生成された対象となるクラスターと同一ではない可能性があることに留意すべきである。コンピューティングサーバー１３０は、非サンプル化グラフで生成された対象となるクラスターに割り当てられたノードの点で、閾値の重なり度を有するクラスターを同一の対象となるクラスターとして扱ってもよい。ノードの一定の割合（例えば、60〜80%）がサンプリングされる毎に、対象となるノードがサンプリングされ、サンプリングされたグラフのいくつかにおいて、選択されてもよい。対象となるノードがサンプリングされるそれらのサンプリングされたグラフに対し、コンピューティングサーバー１３０は、対象となるノードが対象となるクラスターに分類される回数を決定する。例えば、サンプリング及びコミュニティ検出プロセスは、20〜100回繰り返されてもよい。対象となるノードが、例えば14個の異なるサンプリングされたグラフに現れる場合、対象となるノードが対象となるクラスターに分類される回数は、0〜14回であってもよい。コンピューティングサーバー１３０は、対象となるクラスターに対する対象となるノードの安定性の因子の値を導出する。安定性の因子は、対象となるノードが対象となるクラスターに分類される回数と、対象となるノードがサンプリングされたグラフに現れる回数との比となり得る。安定性の因子が閾値（例えば、25%）を超える場合、コンピューティングサーバー１３０は、マルチパス階層アプローチにおけるコミュニティ検出の別のラウンドのため、ステップ８４０において、対象となるノードを対象となるクラスターに追加する。相対的に低い閾値（例えば、50%より低い）を設定して、対象となるノードを１つ以上のクラスターに追加してもよい。
【００８９】
また、コンピューティングサーバー１３０は、コミュニティのための参照パネルサンプルを決定するために安定性分析を用いてもよい。例えば、対象となるコミュニティにより一貫して割り当てられているノードを見つけるために、その対象となるコミュニティに対して、同じ安定性分析を実行してもよい。参照パネルサンプルを選択する際、より高い閾値（例えば、80%、90%）を安定性の因子に用いてもよい。サンプリングされる毎にノードが一貫して対象となるコミュニティに割り当てられていることは、そのノードが対象となるコミュニティの代表的な遺伝データセットとして機能する可能性があることを示している。そのようなノードは、参照パネルサンプルとして選択されてもよい。
【００９０】
図９は、一実施形態による、マルチパスコミュニティ検出アプローチにおける例示的なクラスタリング処理を示している。ノード９１０は、対象となるノードである。第１レベルのコミュニティ検出に対し、対象となるノード９１０は、２つのクラスターに含まれている。また、第２のパスに対しては、対象となるノードは、２つのサブクラスターに含まれている。このように、図９は、対象となるノード９１０を３つの異なるコミュニティまたはサブコミュニティに割り当てるための、少なくとも３つのパスを示している。
【００９１】
コミュニティ分類
図１０は、一実施形態による、対象となる個体のコミュニティを検出するためのプロセスを描いたフローチャートを示している。コンピューティングサーバー１３０は、１つ以上のトレーニングされた機械学習モデルを用い、与えられた対象となる個体について、その対象となる個体をコミュニティに割り当てるためのスコア（例えば、確率）を計算する。モデルは、既存の個体、例えば、遺伝データストア２１０に存在する誰か、またはコンピューティングサーバー１３０に含めるためにDNAサンプルを提出した新しいユーザーを分類するために使用されてもよい。
【００９２】
コンピューティングサーバー１３０は、対象となる個体の遺伝データセットを引き出す１０１０。また、コンピューティングサーバー１３０は、参照パネルサンプルストア２４０から複数の参照パネルサンプルを引き出す１０２０。各参照パネルサンプルは、参照パネルの個体を表す。参照パネルの個体の少なくとも一部は、フルIBDネットワークからフィルタリングされたIBDネットワークによって生成される。フィルタリングされたIBDネットワークは、図４から図９を参照して説明したように、エッジまたはノードの１つ以上の特徴に基づいてフィルタリングされた、ノードのサブセットを含む。
【００９３】
コンピューティングサーバー１３０は、対象となる個体に関連付けられたIBD親和性を生成１０３０する。各IBD親和性は、例えば、対象となる個体の遺伝データセットと参照パネルサンプルのフェージングされた遺伝データセットを比較することにより、対象となる個体の遺伝データセットと参照パネルサンプルの１つとを比較することで決定される。コンピューティングサーバー１３０は、１つ以上のコミュニティ分類器を引き出す１０４０。各コミュニティ分類器は、個体が遺伝コミュニティに属しているかどうかを決定するためにトレーニングされたモデルとなり得る。コンピューティングサーバー１３０は、各コミュニティ分類器のための特徴のセットを生成１０５０する。いくつかの実施形態においては、いくつかの分類器は、IBD親和性または対象となる個体の遺伝データセットを特徴量として受信することができる。他の実施形態では、コンピューティングサーバー１３０は、IBD親和性（および、いくつかの実施形態では、民族性の推定値）および遺伝データセットを、各モデルのために選択された特徴に応じて特徴ベクトルに変換してもよい。各モデルは、どの特徴が選択され、その特定のモデルをトレーニングするために使用されたかに応じて、異なる特徴ベクトルを受信する。
【００９４】
識別されたコミュニティまたはサブコミュニティについて、コンピューティングサーバー１３０は、選択された特徴量を有するトレーニングセットを用い、そのコミュニティのための分類器モデルをトレーニングしてもよい。一例として、コンピューティングサーバー１３０は、分類に使用される特徴として、高い予測能力を有すると推定される特徴を選択してもよい。特徴は、遺伝データセット、IBD親和性値、民族性推定値などから抽出されてもよい。特徴量のセットは、様々なコミュニティごとに異なってもよい。特徴の選択をするために用いられ得るアルゴリズムの例としては、スパースペナルティ回帰（例えば、ラッソ回帰）、フォワード／ステップワイズ回帰法、再帰的特徴除去、および正則化ツリーなどが挙げられるが、これらに限定されるものではない。コンピューティングサーバー１３０は、そのコミュニティに対して選択された特徴量のセットを使用し、対応するモデルをトレーニングする。トレーニングが完了すると、モデルは対象となる個体について、その個体のコミュニティへの割り当てを予測するためのスコア、または尤度を生成することができる。一実施形態では、モデルは確率（0から1の間の実数）を出力し、1に近い数字はその個体が高い信頼性でコミュニティに分類されていることを示し、0に近い数字はその個体が高い信頼性でコミュニティのメンバーではないことを示す。
【００９５】
トレーニングセットは、１つ以上のコミュニティに分類された既知の個体の特徴を含んでいる。モデルの対象となるコミュニティの一部で、ある個体はそのコミュニティに分類されるべきであることを示す"１"のトレーニングラベルが割り当てられる。他のコミュニティに属している個体には、そのコミュニティに分類されるべきでないことを示す「0」のトレーニングラベルが割り当てられる。一実施形態では、トレーニングラベルの分類は、特定のコミュニティに関連する個体の安定性スコアに基づいてもよい。例えば、一実施形態では、第１の閾値よりも大きいコミュニティの安定性スコアを有する個体は"１"のトレーニングラベルが割り当てられ、第２の閾値よりも小さいコミュニティの安定性スコアを有する個体は"２"のトレーニングラベルが割り当てられる。一実施形態では、第１の閾値と第２の閾値との間の安定性スコアを有する個体は、トレーニングに使用されない。一実施形態では、個体はモデルトレーニングアルゴリズムへの入力として提供されるトレーニングセットを構築するため、およびモデルのトレーニングに使用するために、IBDネットワーク（フィルタリングされたもの、またはフル）および／または参照パネルサンプルからランダムに引き出される。他の実施形態では、入力データは異なるように選択されてもよい。個体に関連するデータは、モデルのための特徴量に変換される。
【００９６】
適切な機械学習モデル構造、教師ありまたは教師なしを、モデルのトレーニングのために使用してもよい。例示的な構造は、ランダムフォレスト、サポートベクターマシン（SVM）、ロジスティック回帰、ニューラルネットワークなどが挙げられるが、これらに限定されるものではない。各モデルは、重みのセットに関連付けられていてもよい。トレーニング工程は、トレーニングセットを用いて分類結果を決定し、トレーニングラベルに基づいてモデルの誤差を低減または最小化するようにモデルの重みを調整することを含む。重みの調整は、座標降下、確率的座標降下などの１つ以上の技法を含んでもよい。トレーニングは、設定された反復回数（例えば、エポック数）を終えた後、または誤差率がもはや改善されない（例えば、モデルが収束した）後に完了するように決定されてもよい。分類器モデルは１つのコミュニティに特化してトレーニングすることができるが、マルチコミュニティのためのマルチクラスの分類器も可能である。複数のコミュニティについては、マルチモデルがトレーニングされてもよい。コンピューティングサーバー１３０は、トレーニングされたモデルの重みを含んだモデルを、コミュニティ分類器として記憶する。
【００９７】
コミュニティ分類器がトレーニングされた後、コンピューティングサーバー１３０は、各コミュニティ分類器に対し、対象となる個体が遺伝コミュニティに属しているかどうかを決定するために、対象となる個体に関連付けられた特徴のセットをコミュニティ分類器に入力１０６０する。これは、各モデルについて確率などのスコアを計算することを含んでもよい。一実施形態では、トレーニングされたモデルによって計算された確率が閾値の数値を超える場合、個体は所定のコミュニティに属するものとして分類される。個体をコミュニティに分類するための閾値は、各モデルに対して同じであってもよいし、異なっていてもよい。コミュニティ予測モジュールの出力は、分類と、各コミュニティに対する事後確率（例えば、分類が正しいかどうかの信頼度）の両方を含んでもよい。
【００９８】
コンピューティングサーバー１３０は、対象となる個体が属する１つ以上の遺伝コミュニティを要約したレポートを生成１０７０する。ユーザーベースの広範な遺伝的多様性、異なるユーザーに対するIBD親和性の質の変化、IBDネットワーク内で識別されるコミュニティの構成の不均一性などの様々な要因のために、個体は0、1つ、またはそれ以上のコミュニティのメンバーであると予測されてもよい。一実施形態では、コミュニティ予測モジュールの出力は、生成されたドキュメントまたはGUIを介してユーザーに報告されてもよい。ドキュメントまたはGUIで報告されるデータは、コミュニティに関連付けられた注釈、およびコミュニティに関連付けられた注釈の要約から引き出される歴史的または地理的解釈に基づいてもよい。これには、コミュニティを特徴づける地理的特徴または地域、および注釈によって知らされているかもしれない、または知らされていないかもしれない、コミュニティに特徴的な他の歴史的、社会的または経済的特徴が含まれていてもよい。さらに、コンピューティングサーバー１３０は、IBDコネクションおよび各コミュニティに関連する他の遺伝的推定値を要約したレポートを生成してもよい。例えば、ユーザーと同じコミュニティに属していると分類される第２のいとこの数の推定値が報告されてもよい。
【００９９】
コンピューティングマシンのアーキテクチャ
図１１は、コンピュータ可読メディアから命令を読み取り、プロセッサー（またはコントローラ）で命令を実行することができる、例示的なコンピューティングマシンのコンポーネントを示すブロック図である。本明細書に記載されたコンピュータは、図１１に示された単一のコンピューティングマシン、仮想マシン、図１１に示されたコンピューティングマシンの複数のノードを含む分散コンピューティングシステム、または他の任意で適切なコンピューティングデバイスを含むことができる。
【０１００】
例により、図１１は、本明細書で論じられている任意の１つ以上のプロセスをマシンに実行させるための指示１１２４（例えば、ソフトウェア、プログラムコード、またはマシンコード）がコンピュータ可読メディアに記憶されていてもよい様な、コンピュータシステム１１００の例示的な形態のコンピューティングマシンを示している。いくつかの実施形態では、コンピューティングマシンは、スタンドアロンデバイスとして動作するか、または他のマシンに接続されていてもよい（例えば、ネットワーク化されていてもよい）。ネットワーク化された展開では、マシンはサーバークライアントネットワーク環境におけるサーバーマシンまたはクライアントマシンの能力で動作してもよいし、ピアツーピア（または分散型）ネットワーク環境におけるピアマシンとして動作してもよい。
【０１０１】
図１１に記載されたコンピューティングマシンの構造は、クライアントデバイス１１０、コンピューティングサーバー１３０、および図２に示された様々なエンジン、インターフェイス、端末、および機械を含むが、これらに限定されない図１および図２に示された任意のソフトウェア、ハードウェア、または組み合わせたコンポーネントに対応することができる。図１１は、様々なハードウェアおよびソフトウェア要素を示しているが、図１および図２に記載された構成要素の各々は、追加の要素を含んでもよいし、より少ない要素を含んでもよい。
【０１０２】
コンピューティングマシンの例としては、パーソナルコンピュータ（PC）、タブレットPC、セットトップボックス（STB）、パーソナルデジタルアシスタント（PDA）、携帯電話、スマートフォン、ウェブアプライアンス、ネットワークルータ、モノのインターネット（IoT）デバイス、スイッチまたはブリッジ、またはそのマシンによって実行されるべきアクションを指定する指示１１２４を実行することが可能な任意のマシンであってもよい。さらに、単一のマシンのみが例示されているが、「マシン」および「コンピュータ」という用語は、本明細書で議論される方法論のうち、任意の１つ以上を実行するために個別にまたは共同で指示１１２４を実行する任意のマシンの集合体を含むと取られてもよい。
【０１０３】
例示的なコンピュータシステム１１００は、CPU（中央処理装置）、GPU（グラフィックス処理装置）、TPU（テンソル処理装置）、DSP（デジタル信号プロセッサー）、システムオンチップ（SOC）、コントローラ、状態装置、アプリケーション専用集積回路（ASIC）、フィールドプログラマブルゲートアレイ（FPGA）、またはこれらの任意の組み合わせなどの1つ以上のプロセッサー１１０２を含む。また、コンピューティングシステム１１００の一部は、指示がプロセッサー１１０２によって直接または間接的に実行されたとき、プロセッサー１１０２に特定の動作を実行させることができる指示１１２４を含むコンピュータコードを格納するメモリー１１０４を含んでもよい。指示は、装置可読命令、ソースコードを含むプログラミング指示、および他の通信信号や指示など、異なる形態で記憶され得る、任意の指揮、命令、指令であってよい。指示は、一般的な意味で使用されてもよく、機械読み取り可能なコードに限定されない。
【０１０４】
本明細書に記載の１つ以上の方法は、プロセッサー１１０２の動作速度を改善し、メモリー１１０４に要求されるスペースを削減する。例えば、本明細書に記載の機械学習方法は、プロセッサー１１０２のトレーニング、収束に到達するステップ、および結果を生成するステップを簡略化する１つ以上の新規な技法を適用することにより、プロセッサー１１０２の計算の複雑さを低減する。また、本明細書に記載されたアルゴリズムは、モデルおよびデータセットのサイズを縮小して、メモリー１１０４のために必要な記憶領域を縮小する。
【０１０５】
特定の動作性能は、単一のマシン内に存在するだけでなく、いくつかのマシンにまたがって配置された、多数のプロセッサー間に分散されてもよい。いくつかの例示的な実施形態では、１つ以上のプロセッサーまたはプロセッサー実装モジュールは、単一の地理的な場所（例えば、家庭環境、オフィス環境、またはサーバファーム内）に配置されてもよい。他の例示的な実施形態では、１つ以上のプロセッサーまたはプロセッサー実装モジュールは、いくつかの地理的な場所に分散していてもよい。本明細書または特許請求の範囲では、プロセッサーによって実行されるいくつかのプロセスを参照することができるとしても、これは、多様に分散されたプロセッサーの共同動作を含むと解釈されるべきである。
【０１０６】
コンピュータシステム１１００は、バス１１０８を介して互いに通信するように構成されたメインメモリー１１０４および静的メモリー１１０６を含んでもよい。さらに、コンピュータシステム１１００は、グラフィックスディスプレイユニット１１１０（例えば、プラズマディスプレイパネル（PDP）、液晶ディスプレイ（LCD）、プロジェクタ、またはブラウン管（CRT））を含んでもよい。プロセッサー１１０２によって制御されるグラフィックディスプレイユニット１１１０は、本明細書に記載されたプロセスによって生成された１つ以上の結果およびデータを表示するためのグラフィカルユーザーインターフェイス（GUI）を表示する。また、コンピュータシステム１１００はアルファニューメリック入力装置１１１２（例えば、キーボード）、カーソル制御装置１１１４（例えば、マウス、トラックボール、ジョイスティック、モーションセンサ、または他のポインティング器具）、ストレージユニット１１１６（ハードドライブ、ソリッドステートドライブ、ハイブリッドドライブ、メモリディスクなど）、信号発生装置１１１８（例えば、スピーカ）、およびネットワークインターフェイス装置１１２０を含んでもよく、これらは、バス１１０８を介して通信するように構成される。
【０１０７】
ストレージユニット１１１６は、本明細書に記載された方法論または機能のうちの任意の１つ以上を具現化する指示１１２４が格納されたコンピュータ可読メディア１１２２を含む。また、指示１１２４はコンピュータシステム１１００の実行中に、完全にまたは少なくとも部分的に、メインメモリー１１０４内またはプロセッサー１１０２内（例えば、プロセッサーのキャッシュメモリー内）に存在してもよく、メインメモリー１１０４およびプロセッサー１１０２もまた、コンピュータ可読メディアを構成する。指示１１２４は、ネットワークインターフェイス装置１１２０を介し、ネットワーク１１２６上で送受信されてもよい。
【０１０８】
コンピュータ可読メディア１１２２は、例示的な実施形態では単一のメディアであることが示されているが、「コンピュータ可読メディア」という用語は、指示（例えば、指示１１０２４）を格納することができる単一のメディアまたは多様なメディア（例えば、集中型または分散型のデータベース、または関連するキャッシュおよびサーバー）を含むものと取られるべきである。コンピュータ可読メディアは、プロセッサー（例えば、プロセッサー１１０２）によって実行されるための指示（例えば、指示１１２４）を記憶することが可能であり、プロセッサーが本明細書に開示された方法論のうちの任意の１つ以上を実行することを引き起こす任意のメディアを含むことができる。コンピュータ可読メディアは、ソリッドステートメモリー、光学媒体、および磁気媒体の形態のデータリポジトリを含み得るが、これらに限定されない。コンピュータ可読メディアは、伝搬する信号または搬送波のような一過性のメディアを含まない。
【０１０９】
追加考慮事項
前述の実施形態の説明は、例示の目的で提示されたものであり、網羅的なものではなく、また開示された正確な形態に特許権を限定することを意図したものではない。関連する技術の熟練者は、上記の開示に照らして、多くの変更および変形が可能であることを理解することができる。
【０１１０】
本発明による実施形態は、方法およびコンピュータプログラム製品に向けられた添付の請求項に特に開示されており、ここで、１つの請求項のカテゴリー、例えば方法に記載された任意の特徴は、別の請求項のカテゴリー、例えばコンピュータプログラム製品、システム、記憶媒体にも同様に請求することができる。添付の特許請求の範囲の従属項または参考文献は、形式的な理由のみのために選択される。しかしながら、任意の以前の請求項（特に複合的な依存関係）への意図的な参照に起因する任意の主題も同様に請求することができ、それにより、請求項およびその特徴の任意の組み合わせが開示され、添付の請求項で選択された依存関係に関係なく請求することができる。請求することができる主題は、開示された実施形態に記載された特徴の組み合わせだけでなく、異なる実施形態に記載された特徴の他の任意の組み合わせからなる。異なる実施形態で言及された様々な特徴は、例示的な実施形態において、そのような組み合わせまたは配置を明示的に言及して組み合わせることができる。さらに、本明細書に記載または描写された実施形態および特徴のいずれかは、別の請求項および／または本明細書の記載または描写された実施形態または特徴のいずれかとの任意の組み合わせで請求することができる。
【０１１１】
本明細書のいくつかの部分では、情報に対する操作のアルゴリズムおよび記号表現の観点から実施形態を説明している。これらの操作およびアルゴリズムの記述は、機能的に、計算的に、または論理的に記述されているが、コンピュータプログラムまたは同等の電気回路、マイクロコード、またはそれに類似するものによって実装されることが理解される。さらに、一般性を損なうことなく、これらの操作の配置をエンジンと呼ぶことが便利であることも判明している。記載された操作およびそれに関連するエンジンは、ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組み合わせで具現化されてもよい。
【０１１２】
本明細書に記載されたステップ、操作、またはプロセスのいずれかは、単独で、または他の装置と組み合わせて、１つ以上のハードウェアまたはソフトウェアエンジンを用いて実行または実装されてもよい。一実施形態では、ソフトウェアエンジンは、コンピュータプログラムコードを含むコンピュータ可読メディアからなるコンピュータプログラム製品を用いて実装され、このコンピュータプログラム製品は、本明細書に記載されたステップ、操作、またはプロセスのいずれかまたはすべてを実行するためにコンピュータプロセッサによって実行されることができる。用語「ステップ」は、特定の順序を強制するものではなく、また暗示するものでもない。例えば、本開示では、フローチャートに存在する矢印で順次に複数のステップを含むプロセスを記述し得るが、プロセスのステップは、本開示で主張または記載されている特定の順序で実行される必要はない。他のステップが本開示で最初に主張または記載されていたとしても、いくつかのステップが他のステップよりも先に実行されてよい。
【０１１３】
本明細書を通して、複数の例は、単一の例として記述された構成要素、操作、または構造を実装してもよい。２つ以上の方法の個々の操作が図示され、別々の操作として記述されているが、個々の操作のうちの１つ以上は同時に実行されてもよく、操作が図示された順序で実行されることを要求するものはない。例示的な構成において別の構成要素として提示された構造および機能は、結合された構造または構成要素として実装されてもよい。同様に、単一の構成要素として提示された構造および機能は、別の構成要素として実装されてもよい。これらおよび他の変形、修正、追加、および改良は、本明細書の主題の範囲内に収まる。さらに、本明細書および特許請求の範囲で使用される用語"各"は、グループ内のすべての要素またはすべての要素が、用語"各"に関連付けられた記述に適合する必要があることを意味するものではない。例えば、"各部材が要素Ａに関連付けられている"という用語は、すべての部材が要素Ａに関連付けられていることを暗示するものではなく、その代わりに、用語"各"は、単数形で、ある部材（部材の一部）が要素Ａに関連付けられていることを暗示するだけである。
【０１１４】
最後に、本明細書で用いられている言語は、主に可読性と教示の目的で選択されており、特許権を明確にしたり囲んだりするために選択されたものではないことがあり得る。よって、特許権の範囲は、この詳細な説明によってではなく、むしろ、ここに基づいて出願された請求項によって限定されることが意図されている。したがって、本発明の実施形態の開示は、特許権の範囲を限定するものではなく、例示的なものであることが意図されている。
【０１１５】
以下の出願は、すべての目的のためにその全体が参照により組み込まれる。
(1) 2015年10月19日に出願された「Haplotype Phasing Models」と題された米国特許出願第15/591,099号
(2) 2016年5月28日に出願された「Discovering Population Structure from Patterns of Identity-By-Descent」と題された米国特許出願第15/168,011号
(3) 2016年7月13日に出願された「Local Genetic Ethnicity Determination System」と題された米国特許出願第15/209,458号
(4)2013年9月17日に出願された "Identifying Ancestral Relationships Using a Continuous stream of Input "と題された米国特許出願第14/029,765号、
【図１】
2021530026.tif 000004
【図２】
2021530026.tif 000005
【図３Ａ】
2021530026.tif 000006
【図３Ｂ】
2021530026.tif 000007
【図４】
2021530026.tif 000008
【図５】
2021530026.tif 000009
【図６】
2021530026.tif 000010
【図７Ａ】
2021530026.tif 000011
【図７Ｂ】
2021530026.tif 000012
【図８】
2021530026.tif 000013
【図９】
2021530026.tif 000014
【図１０】
2021530026.tif 000015
【図１１】
2021530026.tif 000016
【国際調査報告】
2021530026.tif 000017
2021530026.tif 000018