当前位置：首页 > 化学技术 > 组合技术> 数据解析装置及其方法独创技术50843字

数据解析装置及其方法

2021-04-23 13:07:02

数据解析装置及其方法

　　技术领域tt

　　本发明涉及一种DNA序列的数据解析装置，尤其涉及一种从大规模并行tt型DNA序列装置得到的DNA序列数据的解析技术。tt

　　背景技术tt

　　对于癌、生活习惯病或遗传病等，作为所谓的个别化医疗，需要选择适于tt患者个人的治疗方法，或为了进行恢复后的预测而调查患者个人的遗传性背tt景。因此，进行染色体组或转录物组(转写产物)等的DNA(deoxyribonucleic ttacid，脱氧核糖核酸)序列解析。在此时所使用的DNA序列装置中，只能得tt到被片段化的较短的DNA序列。因此，与较长的参照染色体组序列相比，需tt要调查得到的片段序列是染色体组的哪个部分，并且进行用于调查这里所包含tt的单核苷酸变异(SNP，Single Nucleotide Polymorphism)或插入/缺失等变异tt的数据处理。一般，将这样的数据处理称为匹配处理。tt

　　在所谓的被称为下一代型DNA测序器的大规模并行型DNA测序器中，tt在1次的测量中能够得到数亿个以上的较短的100碱基程度的较长的片段序列tt(前导)。此外，人的情况下，参照染色体组序列的长度约为3千兆碱基(30tt亿碱基)。在匹配处理中，将这些前导序列与参照染色体组序列一个一个进行tt比较来确定对应的位置，确定这里包含的变异。这些需要非常大的计算成本，tt因此开发并利用专用的高效的算法。代表性的方法是将参照染色体组序列通过ttBurrows-Wheeler变换(BWT,Burrows-Wheeler Transformation)(非专利文献tt1)进行数据库化，将前导序列内的较短碱基序列作为检索关键词进行检索，tt在匹配的区域的前后考虑序列错误或变异的可能性而进行比对(非专利文献tt2)。tt

　　一般，在下一代型DNA测序器中产生1％程度的读取错误，此外，在较tt大的染色体组区域中，分散存在多个类似的序列。因此，在每一个前导的匹配tt结果中存在产生错误的可能性。例如，对于某前导序列，在参照染色体组序列tttttt内没有完全一致的区域，但假设少数序列错误时，有时能够发现多处对应的染tt色体组区域。该情况下，选择哪个区域存在任意性，且该判断依赖匹配处理的tt探索方法。因此，为了准确地进行变异解析，在后续的处理，即下游的处理中，tt进行比较多个前导的匹配结果而采用多数决定的再匹配处理(非专利文献3)。tt因此，在进行所有染色体组解析的情况下，通常，对能够覆盖染色体组整体数tt十倍的序列量(数十千兆碱基以上)进行排序。此外，在匹配目的地存在任意tt性时可能产生依存于匹配处理的偏差，因此比较多个种类的匹配工具的结果，tt还要确认没有产生这样的偏差。另外，作为与以上的技术关联的专利文献，例tt如有专利文献1。tt

　　现有技术文献tt

　　专利文献tt

　　专利文献1：日本特开2003－330934号公报tt

　　非专利文献tt

　　非专利文献1：M.Burrows and D.Wheeler:A block-sorting lossless data ttcompression algorithm.Technical Report 124,Digital Equipment Corporation,tt1994.tt

　　非专利文献2：Li H.and Durbin R.(2009)Fast and accurate short read ttalignment with Burrows-Wheeler Transform.Bioinformatics,25:1754-60.tt

　　非专利文献3：McKenna A,Hanna M,Banks E,Sivachenko A,Cibulskis K,ttKernytsky A,Garimella K,Altshuler D,Gabriel S,Daly M,DePristo MA(2010).ttThe Genome Analysis Toolkit:a MapReduce framework for analyzing ttnext-generation DNA sequencing data.Genome Res.20:1297-303.tt

　　非专利文献4：Mantaci,S.,Restivo,A.；Sciortino,M:“An extension of the ttBurrows Wheeler transform to k words.”Data Compression Conference,2005.ttProceedings.DCC 2005.tt

　　非专利文献5：Markus J.Bauer,Anthony J.Cox,Giovanna Rosone:tt“Light-weight BWT Construction for Very Large String Collections,”ttCombinatorial Pattern Matching,Lecture Notes in Computer ScienceVolume 6661,tt2011,pp 219-231tt

　　非专利文献6：Paolo Ferragina,Travis Gagie,Giovanni Manzini:tt“Light-weight Data Indexing and Compression in External Memory,”ttAlgorithmica,July 2012,Volume 63,Issue 3,pp 707-730.tt

　　非专利文献7：Kimura K,Suzuki Y,Sugano S,Koike A:“Computation of ttrank and select functions on hierarchical binary string and its application to genome ttmapping problems for short-read DNA sequences,”J Comput Biol.2009Nov；16tt(11):1601-13.tt

　　非专利文献8：Ge Nong；Sen Zhang；Wai Hong Chan；,"Linear Suffix Array ttConstruction by Almost Pure Induced-Sorting,"Data Compression Conference,tt2009.DCC‘09.,vol.,no.,pp.193-202,16-18March 2009tt

　　发明内容tt

　　发明要解决的课题tt

　　在上述的下游处理中，为了得到较高的精度需要较大的计算成本，因此不tt能一并处理从DNA测序器得到的所有前导。因此，利用采用了高效的算法的tt匹配处理的结果，在要关注的基因区域选择出认为区域引起的可能性较高的前tt导序列，而对这些进行下游解析。tt

　　此外，在另一方面，已知的有：将通过前导长度较长(500碱基程度以上)、tt前导数量较少的(100个程度)的毛细管型DNA测序器进行多次解析而得到tt的前导序列数据数据库化，将染色体组内所关注的基因区域的序列作为查询进tt行同源性检索，对得到的前导序列进行多重比对而进行细菌的识别的方法(专tt利文献1)。然而，将人染色体组通过下一代型DNA测序器进行解析时的数据tt量巨大，达到几十千兆碱基以上，因此在实际运用所能承受的计算时间内不能tt进行同源性检索。tt

　　在进行人的所有染色体组解析的情况下，前导序列数据量多得总序列量达tt到几十千兆碱基，因此尽管采用高效的算法，匹配处理的计算成本也较大，从tt而存在降低该计算成本的问题。tt

　　此外，通过序列错误的处理方法在匹配目的地中存在任意性的情况下，在tt匹配处理中使用探索方法从其中选择匹配目的地表示产生依存于匹配处理的tt偏差。存在如下的问题：提供一种避免这样的探索方法的判断，无论哪个匹配tttttt目的地都能够等价使用的中立的处理方法。tt

　　当前，人的参照染色体组序列除了人白血球抗原(Human LeukocytettAntigen：HLA)区域等特殊的区域外，只有一种。但是，如果准备多种参照tt染色体组序列，则能够从中选择适于患者所属的人种群的序列而进行更精密的tt变异解析。对所有前导序列和参照染色体组序列的组合进行匹配处理，因此变tt更参照染色体组表示重新进行所有的匹配处理。因此，存在如下的问题：分别tt独立处理所有前导序列和参照染色体组序列，能够抑制变换其组合来进行解析tt时的计算成本的增加。tt

　　本发明的目的是提供一种至少解决一个上述课题，而能够降低匹配处理的tt计算成本或能够进行中立的处理的数据解析装置及其方法。tt

　　用于解决问题的手段tt

　　为了实现上述目的，在本发明的具备处理部和存储部的数据解析装置中，tt存储部存储将染色体组序列数据数据库化后的染色体组序列数据库和将前导tt序列数据数据库化后的前导序列数据库，处理部根据特定的解析对象的染色体tt组区域的序列来选择检索用碱基序列即关键序列；求出位于前导序列数据库中tt的关键序列的深度；提取包含位于前导序列数据库中的关键序列的前导序列数tt据，比较提取出的前导序列数据与染色体组区域的序列来进行数据解析。tt

　　此外，为了实现上述目的，在本发明的数据解析装置的处理部的数据解析tt方法中，使用将染色体组序列数据以能够检索的形式数据库化后的染色体组序tt列数据库和将前导序列数据以能够检索的形式数据库化后的前导序列数据库；tt根据特定的解析对象的染色体组区域的序列来选择检索用碱基序列即关键序tt列；求出位于前导序列数据库中的关键序列的深度；提取包含位于前导序列数tt据库中的关键序列的前导序列数据，比较提取出的前导序列数据与染色体组区tt域的序列来进行数据解析。tt

　　发明效果tt

　　根据本发明的解析装置及其方法，能够抑制计算成本。此外，不会发生依tt存于处理方法的偏差，而能够进行中立的处理。tt

　　附图说明tt

　　图1是表示实施例1的用于进行变异解析的处理顺序的流程图。tt

　　图2是用于说明实施例1的通过序列比较来判定有无变异的方法的说明tt图。tt

　　图3是表示实施例1的根据MLU和深度来推定有无变异的方法的流程图。tt

　　图4是对实施例1的由长度不一的多个前导序列构成的数据定义被一般化tt的Burrows-Wheeler变换(BWT)的说明图。tt

　　图5是表示实施例1的使用SLCP(sorted list of cyclic permutations，循环tt序列分类表)来计算字符串w的深度D(w)的方法的说明图。tt

　　图6是说明实施例1的利用BWT时所使用的辅助函数的说明图。tt

　　图7是实施例1的计算针对检索关键序列的深度的流程图。tt

　　图8是表示实施例1的将包含关键序列的所有前导序列根据位于关键序列tt的左方的碱基进行分类来求出相应的前导序列的数量的方法的流程图。tt

　　图9是表示实施例1的BWT的计算方法的流程图。tt

　　图10是表示实施例1的从旧字符串向新字符串的转记方法的说明图。tt

　　图11是表示实施例1的染色体组序列DB和前导序列DB的结构的说明tt图。tt

　　图12是表示实施例1的染色体组坐标x处的MLU值L(x)的计算方法tt的流程图。tt

　　图13是表示实施例2的从所关注的基因区域中，根据MLU和深度来推tt定产生剪接的可能性较高的位置，并且，在推定出的位置，根据序列比较来判tt定有无剪接的方法的说明图。tt

　　图14是用于说明实施例2的在进行正向搜索而推定为有剪接的位置，通tt过序列比较判定有无剪接的处理的说明图。tt

　　图15是表示实施例2的比较前导序列的共同序列S与染色体组序列来判tt定有无剪接的方法的流程图。tt

　　图16是表示实施例2的进行正向搜索在染色体组坐标x，根据MLU和深tt度来推定有无剪接的方法的流程图。tt

　　图17是表示实施例的解析装置的内部的一结构例的框图。tt

　　图18是表示实施例的数据解析方法的处理的式1～式3的图。tt

　　图19是表示实施例的数据解析方法的处理的式4～式7的图。tt

　　具体实施方式tt

　　以下，按照附图说明本发明的各种实施方式，但之前说明本发明的优选方tt式的概要。在本发明的数据解析装置及其方法中，按照词典式顺序tt(lexicographic order)分类所有的前导序列和它们全部的循环置换(cyclic ttpermutation)或后缀(suffix)后数据库化，以任意较短的碱基序列为关键词tt进行检索而能够立即回答包含关键序列的前导数量，并且，能够从所有前导序tt列中立即提取包含关键序列的所有前导序列。tt

　　并且，在参照染色体组序列侧，如果从各碱基位置开始的部分序列达到怎tt样碱基的长度，则在参照染色体组序列内，考虑互补链事先调查是否成为唯一tt而进行数据库化，在任意的碱基位置能够立即回答可保证这样的唯一性的最小tt长度(MLU，minimum length for uniqueness)。通过参照染色体组序列数据单tt独进行这样的计算。因此，只要对参照染色体组序列进行一次计算，就可以对tt任何的前导序列数据进行再次利用。tt

　　并且，在下游的变异解析处理中，1个碱基1个碱基地扫描所关注的基因tt区域内部，在各碱基位置在参照染色体组数据库查询MLU，并且向参照染色tt体组数据库查询而取得长度MLU的染色体组部分序列后，以其为检索关键词tt来向前导序列数据库查询，而得到包含关键序列的前导序列数量(深度，ttdepth)。与周边进行比较而发现深度值大幅度下降的碱基位置时，推定为在此tt包含变异的可能性较高。tt

　　在推定为包含变异的可能性较高的位置，再次在其周边深度没有下降的其tt他位置在参照染色体组数据库查询MLU，并且向参照染色体组数据库查询而tt取得长度MLU的染色体组碱基序列后，以其为检索关键词向前导序列数据库tt查询，来提取包含关键序列的所有前导序列。由此，能够收集来自周边的可能tt性较高的前导序列。以这些为对象，进行详细的变异解析处理。tt

　　实施例1tt

　　实施例1是从关注的基因区域中，根据MLU和深度来推定包含变异的可tt能性较高的碱基位置，并且在推定出的位置，根据序列比较来判定有无变异的tt解析装置以及方法的实施例。tt

　　图1是表示通过本实施例进行变异解析的处理顺序的流程图。另外，实现tttttt各实施例的解析的解析装置通过具有通常的计算机结构的服务器等计算机来tt实现。tt

　　图17表示包含本实施例的所有实施例的解析装置的一结构例。在该图中，tt解析装置1700具备处理部即中央处理部(CPU：Central Processing Unit)1701、tt存储有程序等的存储部即存储器1702、用于操作的GUI(Graphical User ttInterface，图形用户界面)或显示解析结果等的显示部1703、作为存储数据库tt(DB)等的存储部而起作用的硬盘驱动器(HDD)1704、进行参数输入等的tt键盘等输入部1705、用于与网络等连接的网络接口(NIF)1706与总线1707tt连接的结构。存储在HDD1704中的数据库(DB)可以存储在设置于解析装置tt1700的外部的存储装置中，也可以经由网络存储在数据中心等。在以下的实tt施例中说明的各种流程图可以通过CPU1701的程序执行等来实现。tt

　　于是，在图1所示的流程图中，通过大规模并行型DNA测序器102解析ttDNA样品101来得到由多个较短的碱基序列构成的前导序列数据103。与此tt相对，进行前导序列数据库(DB)化处理104，得到前导序列DB105。在前tt导序列DB化处理104中，按照词典式顺序分类所有前导序列和它们所有的循tt环置换(cyclic permutation)或后缀(suffix)。通过该DB化，以任意较短的tt碱基序列为关键词进行检索，而能够立即回答包含关键序列的前导数量(深tt度)，并且，能够从所有前导序列中立即提取包含关键序列的所有前导序列。tt

　　参照染色体组序列数据106通过染色体组序列DB化处理107进行数据库tt化而构建染色体组序列DB108。在参照染色体组DB化处理中，在参照染色体tt组序列的各碱基位置，从此开始的部分序列达到怎样碱基的长度时，在参照染tt色体组序列内考虑互补链调查是否成为唯一后进行存储。通过预先DB化，在tt任意的碱基位置能够立即回答可保证这样的唯一性的最小长度(MLU)。此外，tt能够按照坐标顺序直接存储碱基序列，并立即回答任意指定的坐标范围的碱基tt序列。tt

　　将坐标x处的MLU，即从x开始的部分序列成为染色体组序列内唯一的tt最小长度表示为L(x)。此外，将以从坐标x开始的长度L(x)的染色体组tt部分序列为关键序列时的前导序列的深度表示为x处的深度和D(x)。以下，tt导入图18的式1所示的记法。使用图18的式1的记法时，向染色体组坐标增tttttt大的方向(正向，forward)进行搜索(扫描)的情况下，能够如图18的式2tt所示计算MLU和深度。或者，向染色体组坐标减少的方向(反向,backward)tt进行搜索的情况下，能够如图18的式3所示计算MLU和深度。tt

　　在图1的流程图中，输入用于规定所关注的基因区域的范围的坐标(Xmin,ttXmax)(109)。对于Xmin以上Xmax以下的各x，向染色体组序列DB查询tt而得到MLU，即L(x)的值(110)。此外，向前导序列DB查询而得到各xtt处的深度D(x)(111)。tt

　　然后，输入成为有无变异的推定基准的参数(112)，将x设为关注的区域tt的左端Xmin(113)，开始以下的重复处理。根据MLU和深度，来推定x中tt有无变异(114)。在推定为无变异或不能推定的情况下，立即将x的值更新为ttx+1(120)。不是这样的情况下，根据深度选择一个x附近的其他碱基位置y，tt向染色体组序列DB查询来取得从y开始的长度L(y)的染色体组部分序列tt(115)。以改序列为关键序列，向前导序列DB进行查询来取得包含该序列的tt所有前导序列(116)。详细比较这些前导序列与参照染色体组序列来进行变异tt解析(117)，在发现变异的情况下，将其结果输出给终端(122)或存储装置tt(123)(119)。之后，将x更新为x+1(120)。x没有超过区域的右端时，重tt复处理(121)。不是这样时，结束处理。tt

　　图2是用于说明在上述的实施例1的解析法中，向正向进行搜索，而在推tt定为有变异的位置x，通过序列比较来判定有无变异的方法的说明图。在反向tt搜索的情况下也相同。在图2的图表203中，横轴201表示染色体组位置坐标，tt纵轴202表示计数，并绘制了位置坐标x中的深度D(x)。在SNP位于染色tt体组的位置坐标z的情况下，如204的范围所示，从位置x开始的长度L(x)tt的染色体组部分序列通过z时，深度D(x)的值与周边相比大幅度下降。深tt度下降的位置在正向搜索中位于有变异的位置的相反侧。因此，在深度下降的tt位置x的正向侧的相邻的位置y采用一个深度D(y)没有下降的任意的位置tty。向染色体组序列DB查询而取得从y开始的长度L(y)的染色体组部分序tt列，将该序列作为关键序列而向前导序列DB查询，来收集包含关键序列的所tt有前导序列。tt

　　206表示收集的前导序列，用下划线表示相当于关键序列的部分。205表tttttt示x周边的染色体组序列，用下划线表示相当于关键序列的部分。向染色体组tt序列DB查询而得到x周边的染色体组序列205。收集的前导序列206是大量tt存在的所有前导序列数据的极小一部分，因此能够抑制将它们与x周边的染色tt体组序列205进行比较的计算成本。以关键序列为基准匹配比对这些序列，在tty的反向侧的附近搜索变异。发现变异的情况下(在例子中，在z的位置存在tt从粗体字所示的G向A的单核苷酸变异)，判定为有变异。不是这样的情况下，tt判定为无变异。tt

　　图3是表示在本实施例中，在碱基位置x，根据MLU和深度来推定有无tt变异的方法的流程图。在包含x本身和x周边的各碱基位置y，作为染色体组tt序列DB与前导序列DB的查询结果，设为已取得MLU和深度的值，即L(y)tt和D(y)的值。此外，d1、d2、h1、h2、h3、l1是推定基准参数，在处理之tt前输入它们的值(112)。在位置x深度D(x)充分大时，推定为无变异(301)。tt如果在x的周边MLU变大，则推定为不能推定(302)。如果在x的周边平均tt深度充分变大，则认为不能推定(303)。与周边相比，如果在x深度大幅度降tt低，则推定为有变异，不是这样的情况下，推定为无变异(304)。tt

　　图4是在本实施例，对由长度不一的多个前导序列构成的数据定义被一般tt化的Burrows-Wheeler变换(BWT)的说明图。本来的BWT对1个字符串进tt行定义(参照上述的非专利文献1)，对多个字符串一般化的定义已知有若干tt(参照在本实施例的说明的最后记载的非专利文献4、非专利文献5、非专利tt文献6)。在此，对长度不一的多个字符串，按如下方式进行一般化定义。在tt图4中，为了简单，说明了针对2个前导序列的定义，即使前导序列的数量增tt加几个，也能够同样地进行定义。tt

　　将该图的401和402设为成为对象的2个前导序列。将在这些的尾部附加tt了段落字符$的字符串设为403和404。将作为这些字符串的所有循环置换tt(cyclic permutation)(循环移位cyclic shift)而得到的字符串列表设为405和tt406。综合这些列表后，将按照词典式顺序(lexicographic order)分类而得到tt的字符串的列表设为407。但是，将拉丁字母的比较顺序设为$＜A＜C＜G＜Ttt＜N。在此，将N的顺序设为T之后是因为N是表示A、C、G、T的某个碱tt基的特殊的字符。此外，从最前面字符开始按照顺序比较2个字符串时，在相tttttt同字符位置出现了段落字符$的情况下，不进行从此以后的比较，将它们的顺tt序设为任意。将对这些已分类的字符串的尾部的字符按照分类顺序进行序列而tt得到的字符串设为408。在此，为了便于理解地表示对应关系，竖写字符串408。tt对于前导序列数据(401和402)，在它们的尾部附加段落字符$，将这些全部tt的作为循环置换得到的字符串列表按照词典式顺序分类而得到字符串列表tt(407)，将对得到的字符串列表(407)的尾部的字符按照分类顺序进行序列tt而得到的字符串408定义为前导序列数据(401和402)的BWT。此外，将此tt时在中途得到的407称为已分类循环的置换字符串列表(SLCP,sorted list of ttcyclic permutations)。tt

　　图5是表示在本实施例中，使用SLCP来求出字符串w的深度D(w)的tt方法的说明图。501表示SLCP。连接了501的各要素的尾部的字符是BWT，tt但为了避免繁杂而省略图示。SLCP已按照词典式顺序分类，因此连接了501tt的最前面的字符的字符串成为图19的式4形式的字符串。tt

　　SLCP已按照词典式顺序分类，因此对于由A、C、G、T、N构成的任意tt的字符串w，从最前面的字符按照顺序比较w与SLCP的要素时，能够决定在ttSLCP内出现以w开始的要素紧前面的位置R(w)和紧后面的位置S(w)。tt在此，用0表示SLCP的最初的要素紧前面的位置，用SLCP的所有要素n表tt示SLCP的最后的要素的紧后面的位置。n等于前导序列数据内的总碱基数和tt前导序列数量的和，通过图19的式5来赋予。tt

　　在L S CP内，在w开始的要素只要有1个的情况下成为R(w)＜S(w)，tt其差S(w)-R(w)与在前导序列数据整体中字符串w出现的次数，即w的tt深度D(w)相等。另一方面，在这样的要素1个也没有的情况下成为R(w)tt＝S(w)，这表示不破坏词典式顺序地向SLCP追加w时的插入位置。将(Rtt(w),S(w))称为字符串w的顺序区间。另外，在字符串的比较中，字符tt的比较从最前面字符开始按照顺序进行直到首次出现不同的字符或出现段落tt字符$为止，因此即使在w的尾部字符为$的情况下，也能够决定w的顺序区tt间(R(w),S(w))。tt

　　图6是说明在本实施例中利用BWT时所使用的辅助函数的说明图。BWTtt是连接SLCP(501)的各要素(字符串)的尾部字符而得到的字符串，这些tttttt字符串的长度一般是不同的，但在图6中示例了使这些尾部字符的最右侧一tt致，字符A到处出现的例子。tt

　　对于0以上n以下的任意的整数r和A、C、G、T、N、$的某个字符z，tt用O(z,r)表示在从字符串BWT的最前面字符到第r字符为止的范围内字符ttz出现的次数。关于从字符串的最前面到指定的位置r为止的范围中的特定的tt字符z的出现次数O(z,r)，公知根据等级函数来有效地对其计算的方法(非tt专利文献7)。另外，在r＝n的情况下，对于各z＝$、A、C、G、T、N成为ttO(z,n)＝n(z)，这些值已通过事先扫描1次前导序列数据整体而求出。tt

　　SLCP按照词典顺序被分类，因此按照顺序提取其要素而得的要素也按照tt词典顺序被分类。尤其，对A、C、G、T、N、$的某个字符z，提取了以z开tt始的要素而得的要素，即从R(z)到S(z)的范围按照词典顺序被分类。此tt外，同样地，对A、C、G、T、N、$的某个字符z，提取了以z结束的要素而tt得的要素的整体也按照词典顺序被分类。SLCP由通过循环置换(循环移位)tt生成的所有字符串构成，因此以z开始的要素整体和以z结束的要素整体通过tt循环置换而一对一对应。尤其，对于由A、C、G、T、N构成的任意的字符串ttw，以zw开始的字符串整体与以w开始且在z结束的字符串整体通过循环置tt换而一对一对应。以zw开始的字符串整体通过SLCP内的顺序区间(R(zw),ttS(zw))被给予，以w开始且以z结束的字符串整体在SLCP内的顺序区间tt(R(w),S(w))中通过以z结束的要素整体被给予，这些一般占据SLCPtt的顺序区间(R(w),S(w))内的分散顺序。tt

　　图7是表示在本实施例中，利用该一对一的对应关系计算针对检索关键序tt列的深度的方法的流程图。输入关键序列k(701)，将w设为由k的尾部的一tt字符z构成的字符串(k的后缀,suffix)。对于所有字符u，n(u)的值是已知tt的，因此能够立即计算针对w＝z的R(w)和S(w)的值(702)。后缀w与tt关键序列k一致时，根据R(k)和S(k)的值计算深度D(k)的值后结束tt处理(706)，不是这样的情况下，重复以下的处理(703)。在关键序列k，将tt后缀w之前的符号设为z，利用上述一对一的对应关系，计算R(zw)和S(zw)tt的值(704)。在此，与702同样地，能够计算R(z)的值作为针对比z顺序tt小的字符u的n(u)的总和。将zw设为新的w后(705)，返回703重复进tttttt行处理。tt

　　图8是表示在本实施例中，将包含关键序列的所有前导序列通过位于关键tt序列的左方的碱基进行分类来求出相应的前导序列的数量的方法的流程图。假tt设已经通过上述方法计算出针对关键序列k的S(k)和R(k)的值。对A、ttC、G、T、N、$的各字符z重复以下的处理(803)。利用基于上述的循环置tt换的一对一的对应关系时，能够计算针对字符串zk的深度D(zk)(804)。其tt值为正时(805)，存在D(zk)个包含zk的序列，因此进行报告(806)。tt

　　图8表示使用各碱基将关键序列向左方延长1个碱基而求出各自的深度的tt方法，通过重复进行该方法，使用各种碱基将关键序列向左方延长多个碱基，tt能够计算各自的深度。此外，如果按照各自的深度值所示的重复度重复这些被tt延长的序列，则能够从前导序列数据整体中，包含重复度地提取所有将包含原tt本的关键序列的前导序列向左方延长多个碱基而得到的序列。tt

　　图9是表示在本实施例中，BWT的计算方法的流程图。在BWT的计算tt中，利用基于上述的循环置换的一对一对应关系。tt

　　首先，在901，进行与在SLCP内的$开始的n($)个要素构成的子列表tt对应的处理。将与此对应的BWT的最前面的n($)字符的部分字符串用Q($)tt表示。在Q($)中包含所有的前导序列数据中的碱基字符A、C、G、T、N。tt如果在前导序列数据中包含空的前导序列，则预先去除这些。其结果，在Qtt($)中不包含$。在分类时的字符串比较中，不对$之后的字符进行比较，因tt此Q($)中的字符的序列顺序可以是任意的。因此，将Q($)设为图19的tt式6所示的字符串。用×表示字符的重复，用+或Σ表示字符的连接，由此通tt过在901内所示的公式计算出Q($)。tt

　　此外，在所有的前导序列r的最前面附加段落字符$，生成按照任意顺序tt排列的列表p。p是由属于字符串$的顺序区间的SLCP的要素构成的列表，将ttp的各要素的尾部字符作为BWT的部分字符串登录在Q($)中。此外，将ztt＝$、I($)设为空的数值列表，对于各y＝A、C、G、T、N，将P(y)和P’tt(y)初始化为空列表，Q’(y)初始化为空字符串，将I’(y)初始化为空的tt数值列表，而进行902以后的重复处理。()表示空列表，“”表示空字符串。tt

　　在902，将p设为由属于某字符串w$的顺序区间的SLCP的要素的$之后tttttt的字符串构成的列表，p的各要素的尾部字符已作为BWT的部分字符串登录tt在某Q(y)中，但设为使一对一对应的SLCP的要素(以下，称为位移后的tt要素)的尾部字符尚未登录在哪个Q(y)中，以便实施循环置换而使这些尾tt部字符成为最前面字符。tt

　　通过尾部符号对列表p的各要素进行分类。对于y＝A、C、G、T、N，tt将由在y结束的要素所构成的p的子列表设为p(y)(902)。tt

　　接着，对于y＝A、C、G、T、N，从p(y)的各要素的字符串中删除尾tt部字符y(903)。这些是位移后的要素的$之后的字符串列表。tt

　　对于y＝A、C、G、T、N，将由p(y)的要素中$一字符构成的字符的数tt设为q($,y)，对除此以外的p(y)的要素以尾部的字符x＝A、C、G、T、Ntt进行分类后进行计数，将这些数设为q(x,y)(904)。tt

　　在905，对于各y＝A、C、G、T、N，将在903求出的列表p(y)的要tt素的尾部字符作为BWT的部分字符串登录在字符串Q’(z)之后。在分类时tt的字符串比较中，不对$之后的字符进行比较，因此这些中的字符的排列顺序tt可以是任意的。因此，将连接图19的式7的形式的字符串而得到的字符串设tt为新的Q’(z)(在905内的式中，用×表示字符的重复，用+或Σ表示字符tt的连接)。tt

　　在这些中，关于最初的q($,y)个要素(在尾部具有$)，在901已经将tt位移后的要素的尾部字符登录在Q($)内。另一方面，关于通过剩余的下式tt8表示的个数的要素(在尾部具有A、C、G、T、N某个字符)，位移后的要tt素的尾部字符尚未登录在任何Q(y)中。因此，为了后续的处理，对于各y＝ttA、C、G、T、N，将在列表p’(y)之后连接有列表p(y)的列表设为新的tt列表p’(y)(另外，在图9的905内的式中，用+表示列表的连接)。tt

　　q(A,y)+q(C,y)+q(G,y)+q(T,y)+q(N,y)…(式8)tt

　　此外，在数值列表I’(y)后面追加2个要素：tt

　　q($,y),-(q(A,y)+q(C,y)+q(G,y)+q(T,y)+q(N,y))…tt(式9)。tt

　　在此，正数表示已登录的要素的数量，复数表示反转了在后续的处理中需tt要登录的要素的数量的符号的数量。tt

　　接着，调查数值列表I(z)是否为空(906)。tt

　　在这些不是空的情况下，提取列表最前面要素后删除，并将提取的要素设tt为i。在i为负的情况下，从字符串列表P(z)中提取最前面的(-i)个要素tt后删除，并将由提取出的要素构成的列表设为新的列表p。如905所述，该ptt满足在902假定的条件。因此，返回到902重复进行处理。另一方面，在i为tt正的情况下，使Q(z)的接下来的i个要素位移而得到的要素的尾部字符已tt被登录在某个Q(y)内，因此将这些转记到新的Q’(y)内，而将其转记量tt登录在各I’(y)中(910)。tt

　　此外，在906数值列表I(z)成为空的情况下，调查z是$还是与N相等tt(911)。在z不等于这些的情况下，将z转换为下个顺序的字符Next(z)(912)，tt返回到906继续进行处理。在此，tt

　　Next(A)＝C,Next(C)＝G,Next(G)＝T,Next(T)＝N…(式tt10)tt

　　在911，z与$或N相等的情况下，对于所有的z＝A、C、G、T、N调查ttP(z)是否为空列表(913)。在这些中有空列表的情况下，对所有的z＝A、C、ttG、T、N，将P’(z)、Q’(z)、I’(z)分别设为新的P(z)、Q(z)、I(z)tt(914)，另外将z设为最初的顺序的字符A(915)，返回到906重复进行处理。tt

　　在913，对于所有的z＝A、C、G、T、N，P(z)是空列表的情况下，连tt接字符串Q($)、Q(A)、Q(C)、Q(G)、Q(T)、Q(N)而得到BWT，tt并将其输出(916)。tt

　　图10是表示在图9的910中，从旧字符串Q向新字符串Q’的转记方法的tt说明图。对于各z＝A、C、G、T、N，有表示Q(z)内的转记源的位置的转tt记源指示器，表示Q(z)内的转记目的地的位置的转记目的地指示器。这些tt在处理开始时全部被初始化为0，在910内重复地被更新，在914内全部被复tt位成0。此外，有用于选择转记对象的选择目的地指示器，这些表示Q(A)、ttQ(C)、Q(G)、Q(T)、Q(N)内的某个位置。选择目的地指示器在处理tt开始时被复位成Q(A)的最前面，在910内重复地被更新，在912被复位成tt针对新的z的Q(z)的最先面，在915被复位成Q(A)的最前面。对于旧字tt符串Q，使用选择目的地指示器和转记源指示器这2个种类，因此在图10中，tttttt为了避免混乱，重复显示选择目的地指示器所指示的Q和转记源指示器所指tt示的Q，但这些都是指同一物体。tt

　　为了在910转记从Q至Q’的1个要素，进行如下的处理。首先，读取选tt择目的地指示器所表示的字符串Q(z)内的字符y，使选择目的地指示器前tt进+1。在图10的例子中，z＝A、y＝C。选择Q(y)，将该转记源指示器所tt示的字符(在图中的例子中为T)转记在Q’(y)的转记目的地指示器所示的tt位置上，使转记源指示器、转记目的地指示器都前进+1。为了在910转记从ttQ至Q’的i个要素，使1个要素的转记重复i次。其结果，对于各y＝A、C、ttG、T、N，当Q’(y)的转记目的地指示器前进+i(y)时，在数值列表I’(y)tt的尾部增加i(y)。tt

　　图11是表示染色体组序列DB和前导序列DB的结构的说明图。前导序tt列DB(105)由前导序列(106)的BWT(408)和在BWT上进行等级函数tt的高速计算所需要的辅助表格(1101)构成。染色体组序列DB(108)由按照tt坐标顺序排列的染色体组的碱基序列数据(1102)和MLU数据(1103)构成。tt可以从碱基序列数据(1102)迅速地提取任意指定的范围的碱基序列。MLUtt数据由二进制编码数据(1104)和检索用辅助表格(1105)构成。tt

　　MLU的二进制编码数据(1104)是长度2n的二进制字符串，按如下方式tt构成。首先，将所有要素初始化为0。对于参照染色体组序列的所有碱基位置ttx，计算MLU的值L(x)，作为tt

　　k(x)＝2x+L(x)–1…(式11)tt

　　将二进制编码数据的第k(x)的要素设置成1。但是，可以将最前面要素tt计数为第0的要素。tt

　　在尾部以外的任意染色体组坐标x采用整数l＝L(x)–1时，根据x中tt的MLU的定义，从x开始的与长度l的序列相等的序列位于与x不同的其他tt位置y。此时，忽略最前面的一字符时，从x+1开始的与长度(l-1)的序tt列相等的序列位于与x+1不同的其他位置y+1。因此，根据x+1中的MLUtt的定义，L(x+1)至少必须比(l-1)大。tt

　　因此，成为tt

　　l-1＜L(x+1)∴L(x)-1＝l≦L(x+1)…(式12)tt

　　其结果，成为tt

　　k(x)＝2x+L(x)-1≦2x+L(x+1)＜2x+1+L(x+1)＝k(x+tt1)…(式13)tt

　　即，对于各碱基位置x，k(x)取得不同的值，这些指示二进制编码数据tt的不同的要素。此外，很明显如果x＜y，则k(x)＜k(y)。因此，如果得到tt了二进制编码数据，则能够求出任意染色体组坐标x中的L(x)的值。即，tt求出在二进制编码数据中第x出现1的位置k(x)，按如下方式进行计算即可。tt

　　L(x)＝k(x)-2x+1…(式14)tt

　　将求出在二进制编码数据中第x出现1的位置的函数k(x)＝select(x)tt称为选择函数，使用辅助表格来高效地进行计算的方法是已知的(非专利文献tt7)。1105是在二进制编码数据(1104)上高速地计算选择函数时所使用的辅tt助表格。tt

　　图12是表示本实施例的解析方法中的、染色体组坐标x中的MLU值Ltt(x)的计算方法的流程图。输入参照染色体组序列数据(106)(1201)，生成tt连接双链的参照染色体组序列G(1202)，计算G的后缀阵列(suffix array)ttSA(1203)。SA是按照词典式顺序分类了G的所有后缀(suffix)时，将表示tt后缀的开始位置的整数按照分类顺序排列的整数序列。在人的染色体组的情况tt下，染色体组尺寸为3千兆碱基程度，G的长度为6千兆碱基程度。对于该程tt度大小的G，使用公知的方法(非专利文献8)能够高效地计算SA。SA是将tt后缀的分类顺序变换为开始位置的对应表，但生成其逆变换的对应表即逆后缀tt阵列(ISA,inverse suffix array)(1204)。tt

　　此外，计算G的最长共同前缀长度序列(LCP,longest common prefix length ttarray)(1205)。将按照词典式顺序分类了G的后缀时的第r要素表示为s(r)tt时，LCP为整数序列，将其第r要素定义为s(r)和s(r-1)的最长共同前缀tt长度。能够使用公知的方法(引用—LCP)来高效地计算LCP。将s(r)和之tt前的s(r-1)从最前面字符开始按照顺序进行比较时，第LCP(r+1)+1字tt符的字符不同。同样地，将s(r)和之前的s(r+1)从前缀符号开始按照顺tt序进行比较时，第LCP(r+1)+1字符的字符不同。因此，具有由下式15tt所赋予的长度的s(r)的前缀在染色体组序列G内成为唯一。tt

　　max(LCP(r)+1,LCP(r+1)+1)…(式15)tt

　　在此，max表示采用最大值。因此，可以通过在1206内所示的公式来计tt算能够保证唯一性的序列长度(MLU,minimum length for uniqueness)。tt

　　作为本实施例中的DNA样品，可以使用所有染色体组解析的样品、所有tt外显子组(Exome)解析的样品，或浓缩了所关注的目标区域的DNA片段的tt样品等。tt

　　实施例2tt

　　作为实施例2，说明从关注的基因区域中，根据MLU和深度来推定产生tt剪接的可能性较高的位置，并且，在推定出的位置，根据序列比较来判定有无tt剪接的方法解析装置以及方法的实施例。tt

　　图13是表示在实施例2，用于进行转录物组的剪接解析的处理顺序的流tt程图。tt

　　通过大规模并行型DNA测序器(102)解析cDNA样品(1301)来得到tt由多个较短的碱基序列构成的前导序列数据(103)。以下，与实施例1同样地，tt进行前导序列DB化处理(104)，得到前导序列DB(105)。tt

　　对于参照染色体组序列数据(106)，与实施例1同样地，通过染色体组序tt列DB化处理(107)进行数据库化来构筑染色体组序列DB(108)。tt

　　输入用于规定所关注的基因区域的范围的坐标(Xmin,Xmax)(109)。对tt于Xmin以上Xmax以下的各x，与实施例1同样地，向染色体组序列DB查tt询而得到MLU，即L(x)的值(110)。此外，向前导序列DB查询而得到各ttx中的深度D(x)(111)。tt

　　输入成为剪接的有无推定基准的参数(1312)，作为关注x的区域的左端ttXmin(113)，开始以下的重复处理。根据MLU和深度来推定x中有无剪接tt(1314)。推定为无剪接或不能推定的情况下，立即将x的值更新为x+1(120)。tt不是这样的情况下，根据深度选择一个x附近的其他碱基位置y，从y开始向tt染色体组序列DB查询而取得长度L(y)的染色体组部分序列。以这些为关tt键序列，向前导序列DB进行查询而取得包含这些的所有前导序列(116)。通tt过比较这些前导序列与参照染色体组序列来进行剪接的有无的判定(1317)。tt在判定为有剪接的情况下，将其结果输出给终端(122)或存储装置(123)(119)。tttttt之后，将x更新为x+1(120)。如果x没有超过区域的右端，则重复处理(121)。tt不是这样的情况下，结束处理。tt

　　图14是用于说明在本实施例，在正向(染色体组坐标增大的方向)进行tt探索而推定为有剪接的位置x，通过序列比较来判定剪接的有无的处理的说明tt图。在反向搜索的情况下也相同。横轴1401表示染色体组位置坐标，纵轴1402tt表示计数，图表1403绘制了位置坐标x中的深度D(x)。染色体组坐标在ztt位置，在其反向侧(染色体组坐标减少的方向)具有将z设为终端的内含子，tt在其正向侧产生具有外显子组那样的剪接。如1404的范围所示，将从位置xtt开始的长度L(x)的染色体组部分序列包含在内含子内部或通过z时深度Dtt(x)的值与z的正向侧的周边相比大幅度下降。即，以z为边界，在z的反tt向侧与z的正向侧相比深度大幅度下降。tt

　　因此，对于与正向侧相比成为在反向侧深度大幅度下降的边界的位置坐标ttx，在x的正向侧的附近取得一个深度没有下降的任意的位置y。从y开始向tt染色体组序列DB查询而取得长度L(y)的染色体组部分序列，将该序列作tt为关键序列向前导序列DB进行查询，而收集包含关键序列的所有前导序列。tt1405表示x周边的染色体组序列，用下划线表示相当于关键序列的部分。1406tt表示收集的前导序列，用下划线表示相当于关键序列的部分。向染色体组序列ttDB查询而得到x周边的染色体组序列1405。tt

　　收集的前导序列1406是大量存在的所有前导序列数据的极小一部分，因tt此能够抑制以下处理的计算成本。1411表示前导的共同序列S。它是将属于tt1406的前导序列在关键序列的位置匹配进行比对，排列各碱基位置中以最高tt频率出现的碱基而得到的序列。在共同序列S上，使用延长在关键序列(下划tt线部分)对应的染色体组序列G的碱基位置坐标而得到的坐标系(1412)。对tt共同序列S进行解析而检测出剪接的情况下，报告该剪接。tt

　　在此，为了表示共同序列S的部分字符串、染色体组序列数据以及前导序tt列数据中的其深度，导入下式16所示的记述方法和用语。tt

　　S[z0,z1]：位置坐标为z0以上z1以下的S的部分序列tt

　　Occ(s,G)：碱基序列s作为G的部分序列而出现的次数(出现次数)tt

　　(染色体组序列数据中的s的深度)tt

　　Occ(s,R)：碱基序列s作为R的部分序列而出现的次数(出现次数)tt

　　(前导序列数据中的s的深度)tt

　　Loc(s,G)：碱基序列s作为G的部分序列而唯一出现时的出现位置坐标tt

　　(Occ(s,G)＝1时)…(式16)tt

　　在此，可以通过在实施例1使用图7说明的方法高效地计算出前导序列数tt据中的s的深度。此外，也可以使用参照染色体组序列G的BWT同样地计算tt出染色体组序列数据中的s的深度。可以根据G的后缀阵列直接计算出G的ttBWT，如实施例1所述可以使用公知的方法高效地计算出参照染色体组序列Gtt的后缀阵列(非专利文献8)。此外，碱基序列s作为G的部分序列而出现的tt位置唯一时，可以使用G的BWT高效地计算出其位置坐标是公知的(非专利tt文献7)。tt

　　图15是表示在本实施例中，比较前导序列的共同序列S与x周边的染色tt体组序列来判定在x位置有无剪接的方法的流程图。在此，p0、p1、p2、p3tt是由用户指示的判定基准参数。首先，将变量x1初始设定成推定为有剪接的tt位置坐标x(1501)。比较x1与x(1502)，两者相距p0以上的情况下，判定tt为无剪接，结束处理(1517)。不是这样的情况下，更新x0的值(1503)，决tt定S的部分序列s(1504)。计算染色体组序列数据中的s的深度Occ(s,G)tt(1505)，在其比1大的情况下，向x0的更新处理1506前进。除此以外的情tt况下，在Occ(s,G)等于1的情况下(1509)，在前导序列数据中的s的深度ttOcc(s,R)比p1大的情况下(1510)，向1511前进。另一方面，在Occ(s,G)tt为0的情况下(1509)或Occ(s,R)在p1以下的情况下(1510)，向x1的更tt新处理1508前进。此外，在x0的更新处理(1506)后，确认共同序列S是否tt决定至x0，这样的情况下，返回到1504，更新s而继续进行处理。tt

　　不是这样的情况下，向x1的更新处理1508前进而继续进行处理。向1511tt前进的情况下，求出s的唯一出现位置v，如果从x到v的距离在p2以下，tt则判定为检测出p2以下的长度较短的缺失(1513)，判定为无剪接(1517)，tt结束处理。不是这样的情况下，v位于x的左方，并且，从x到v的距离在s3tt以下的情况下(1514)，判定为有剪接而结束处理(1515)。不是这样的情况下，tt判定为检测出嵌合基因(融合基因)(1516)，判定为有剪接(1515)，结束处tttttt理。tt

　　图16是表示在本实施例中，正向进行搜索在碱基位置x，根据MLU和深tt度来推定有无剪接的方法的流程图。在包含x本身和x周边的各碱基位置y，tt作为染色体组序列DB与前导序列DB的查询结果，设为已取得MLU和深度tt的值，即L(y)和D(y)的值。此外，d1、d2、h1、h2、h3、h4、l1是推定tt基准参数，在处理之前输入这些值。在位置x深度D(x)充分大时，推定为tt无剪接(1601)。如果在x的周边MLU变大，则推定为不能推定(1602)。如tt果在x的正向侧的周边平均深度充分变大，则认为不能推定(1603)。与X的tt正向侧的周边相比，如果在x的反向侧的周边深度大幅度降低，则推定为有剪tt接，不是这样的情况下，推定为无剪接(1604)。tt

　　在以上说明的本发明中，对于各前导序列，考虑序列错误的各种可能性，tt不进行任何调查其匹配目的地的处理。对于前导序列数据，按照词典式顺序分tt类(包含前导序列本身)其所有的后缀。这样的分类处理较简单，不会留下任tt何的任意性。因此，不会发生依存于处理方法的偏差，能够进行中立的处理。tt此外，由于处理简单，与匹配处理进行比较，而能够抑制计算成本。tt

　　此外，完全独立地进行参照染色体组侧的MLU的计算和前导序列侧的所tt有后缀的分类处理。因此，在准备了多个参照染色体组序列的情况下，不需要tt进行依存于参照染色体组和前导序列的组合的处理。tt

　　并且，在下游的变异解析处理中，在想要解析的基因区域内，通过进行向tt参照染色体组序列数据库的查询(MLU，或MLU的长度的部分序列)和向前tt导序列数据库的查询(针对关键序列的深度、或包含关键序列的前导序列)，tt推定包含变异的可能性较高的区域，从所有前导序列中检索成为对象的前导序tt列而能够进行详细的解析。因此，不进行以往的匹配处理，通过本发明检索对tt象而能够高效地进行变异解析。tt

　　另外，本发明并不局限于上述的实施例，还可以包括各种变形例。例如，tt上述的实施例是为了更好地理解本发明而进行的详细说明，并不一定必须具备tt说明的所有结构。此外，也可以将一实施例的结构的一部分置换成其他实施例tt的结构,并且,也可以对一实施例的结构增加其他实施例的结构。此外，可以对tt各实施例的结构的一部分进行其他结构的追加/删除/置换。tt

　　并且，上述的各结构、功能、处理部等说明了生成用于实现这些的一部分tt或全部的程序的例子，但这些的一部分或全部例如也可以通过集成电路进行设tt计等而通过硬件来实现。tt

　　符号说明tt

　　100、122 用户终端tt

　　101 DNA样品tt

　　102 大规模并行型DNA测序器tt

　　103 前导序列数据tt

　　104 前导序列数据库(DB)化处理tt

　　105 前导序列数据库(DB)tt

　　106 参照染色体组序列数据tt

　　107 染色体组序列数据库(DB)化处理tt

　　108 染色体组序列数据库(DB)tt

　　123 磁盘tt