TW200419423A

TW200419423A - Method for determining sequence alignment significance

Info

Publication number: TW200419423A
Application number: TW093103503A
Authority: TW
Inventors: Aleksandar Poleksic
Original assignee: Eidogen Inc
Priority date: 2003-02-14
Filing date: 2004-02-13
Publication date: 2004-10-01
Also published as: US20040167720A1; US6988039B2; WO2004074990A2; WO2004074990A3

Description

200419423 玫、發明說明：美國專利申請案相關申請案交互參考不適用關於聯邦贊助之研究或開發之聲明不適用電腦程式附錄參考不適用【發明所屬之技術領域】之計算方法之領、本發明係、關於用於決定基因組序列關係所包含之基因在5_與-，_之間。目另ιί蛋"白貝举妨^日碑蛋白質家r:: ^九木中於較小數目的「藥物證1 资白貝豕無例如激酶、蛋白白質、捕“ 蛋白酶、核激素受體、橫跨膜的貝趨化因子及細胞因子。& $ & & _ + 物$每n 此專蛋白質家族係稱作广 ^ ^ ^ 叼杀物與已生效並篩選之目桿, 基於在此等家族中所找到、放市場之數目…… 為了表大化新藥物- 勿 < 要c a (目刖樂物開發項畔多八一Ί不、乐乂貝目令僅大約5%進入市場） a,r ^ Μ ^ ,,.. 门源投咢將其研究定向於言別亚特徵化樂物證實蛋白質家族之新賴成員。序列對齊方法可應用於基因組盥士店、目丨丨太从 ”蛋白貝體序列且嘗試義由積測-查询序列與具有 Αν Η ^ ^ ^ 傅^功此之其他序列之舞似〖生；4別一給定序列之在一序列與另一序列係同

O:\9I\91I45 DOC 200419423 的-構一預期兩基因、兩基因產物或蛋白質共有類似目標二:因而1已知基因表示產物係-藥物俨對肖同源建模方法來識別與可能的新穎藥物目因/CDNA序列。此外，在藉由其他技術恤目払之結構與功能之方面，例如決，、其三維結構或者活性部位或蛋白質與蛋白質相互:用力存在’可向可能的藥物目標進行類似的結構在序列比較方法用於目標識別與特徵化令，該方法可藉由比較具有已知功能之6敕从力此之凡整的cDNA副本或cDNA片斷之列與基因DNA而用於決定基因函數地圖。基因函數用於開發驗抽綁藥物，其打開·閉一基因或基因馨。藉由將已知蛋白質藥物目標之完整的CDNA副本或cDNA 片斷之間之序列相關或序列同源與未知基因表示產物之完整的cDNA副本或eDNA片斷進行比較，基於序列比乾方: 之同源建模可用以識別並特徵化可能的蛋白質藥物目乂標之功月b、二維結構與活性區域。 /、序列比較方法、BLAST演算法、隱式馬可夫模型及时密斯-沃特曼為基礎之技術基於兩序列之序列類似性才曰派-對齊分數。-未正規化的原始對齊分數係基於剩餘代換機率、剩餘插入/刪除懲罰及背景剩餘機帛。兩序列之間的最高得分對齊係稱作最佳對齊。之為了確保-對齊分數在統計上係有意義的_即為了顯_ -特定對齊分數不同於對齊兩隨機序列所預期之對齊二

O:\91\91145.DOC 4

馨 -6- 200419423 之轾度-對原始對齊分數進行正規化係必要的。在本項技術中，用於表示一原始對齊分數是否在統計上係有意義之最普通測量之一係使用對齊分數之1}值。一原始對齊分數\之？值提供找到與具有至少x之分數s之一對齊機率用於對齊所隨機選取與產生對齊分數义之此等序列具有相同長度之兩序列。已顯示當不允許間隙且在較大序列長度❿與n限制下’分數X之P值可表示成： P(S 之 X)» i 一 exp(—Kmne'h) ^ 其中λ與κ係縮放參數。參見美國國家科學院刊87(199〇)第 2264至2268頁由Kadin，s·與Altschul，S.F·所著之藉由使用通用得分概要用於評估分子序列特徵之統計重要性之方法；Ann. Pr〇b. 22(1994)第 2022 至 2039 頁由 Dembo，A·、

Karlin，S·與Zeitouni，〇·所著之最大非對齊兩序列段分數之限制分佈。因而將此等參考文獻及其他每一參考文獻全部併入本文，如同在本文中已完全說明。許多計算實驗表明應將相同的公式應用於間隙序列對齊之統計中。在此情形中，必須從對隨機序列進行之一大規模比較中確定1與κ。將始終稱為ρ(χ|κ，λ)。已採用許多近似法來估計P(Sh)。PSI_BLAST之最近版本 (一般當作BLAST演算法中最敏感的）使用島統計為複數個具有不同長度之所隨機產生之序列對、複數個代換矩陣及複數個間隙懲罰預計算縮放參數人與尺。選擇隨機序列中的剩餘頻率以反映背景剩餘頻率。對於每一查詢/樣板序列對，PSI-BLAST調用查找表並基於查詢/樣板序列與隨機產

O:\91\9II45.DOC 200419423 生序列在長度上的類似性且進一步基於間隙得分與用於樣板/查詢對之代換矩陣之同一性來選擇一組特定的預計算九與K參數。雖然在計算上可有效地產生PSI_BLAST查找表二，但其效率以精確性為代價。更特定言t，其假設背景剩餘頻率與長度取樣及間㈣罰申的粒性引人更多誤差。若已為已對齊之每-查詢/樣板對決定㈣κ，則可獲得較高的精確度，但僅以實質上降低PSI_BLAST搜尋速率為代價。島方法島方法係用於決定人與κ並進而由複數個史密斯-沃特曼矩陣決定函數1之-計算上有效之方法。參見關於智慧系統之第七屆國際會議之會議錄（1999年由加拿大蒙羅公園市 ααΑΙ出版社出版)第211至222頁由⑴則，r•、一—h，r· 及Hwa，T所著之為間隙區域對齊快速評估外部統計。史密斯·沃特曼矩陣中每一單元之值對應於在此特定單元處結束之最高得分區域對齊…「島」由與mi元連接之所有此等早7〇組成。向一島所指派之分數係組成該島之此等單元之最高分數。島方法產生大量來自複數個史密斯·沃特曼矩陣之島分數，該等矩陣由1)對齊多個隨機選取之序列；或2)對齊相同兩序列之夕個剩餘「混洗」而形成。由於對於較大的X值，等式1變彳于越來越精確，故藉由僅考慮具有至少c之一分數之此等島可獲得改善的人估計。參見核酸研究29_2(2⑻1)第 351 至 361 頁由 Altschul，S.F.、Bundschuh，R.、〇isen 厌及

Hwa，Τ·所著之為區域對齊分數分佈估計統計參數。Μ。讣μ

O:\91\91145.DOC 200419423 等人已顯示，對於離散對齊分數之情形，k最大概度估計可表示成： “(1 +士） 3 丄：N；€, 4 其中S⑴係第i個島之分數，I丨。φ(ι) —c}且ifg。對於連縯分數之情形，例如對齊序列輪廓時，紅丄。 Α1，等人亦顯示，Κ之最大概度估計可表示成：

A 5

κ rQ 其中A係島搜尋空間之合計搜尋面積。例如，若對具有長度為m與II之兩序列進行、—-jr 1 L io； α » Α 人比較，則Α==細。若進行时此類比較，則A=Bmn。簡化起見，以範齊分數並使用U。關—植5χ連績對

Sc 本發明與對對齊得分執行以島統計為基礎之正規化之— 已改善方法有關。更特定言之，本發明與有效使用島統計來快速決定藉由將—第—序列（通常為查詢序列）盘—第二序列《板序列）對齊所產生之—原始對齊分數之料h 性或不重要性之_啟發式方法有關。因為本發明之方法需要「查找表，者」$所以田師選一較大的樣板序列資料庫日士在對齊敏感度方面可獲得重要改善^於本發明之: 獨立於對齊得分方案、序列長度及其組成，故該等方法！般可應用於任何以動態程式設計為基礎之對齊方法（慮區域對齊）。田；、v 杜所張之方法可同等地由美國專利申吕月案第09/9〇5，176$中所福- 就 P 所揭不之 BLAST、PSI-BLAS丁、

O:\9I\9I145.DOC 200419423 PASTA、HMMER或愛德真（Eidogen)的 STRUCTFAST方法使用。【發明内容】本發明揭示一種用於快速決定藉由將一第一序列與一第一序列對齊所產生之一原始對齊分數之統計重要性之方法與糸統。當相對於非常大數目的樣板序列來對齊一查詢序列時’例如當一生物資訊學家嘗試決定一查詢序列是否與較大序列資料庫例如蛋白質資料儲存庫中之序列之任一者相關時’較佳地可應用所主張發明之方法。通常當執行該對齊研究時，原始對齊分數中絕大多數在統計上並不重要。因而，所主張之方法將允許統計上不重要的此等對齊分數得以快速決定而不會將昂貴的計算資源浪費在計算準確的P值上。該等所主張之方法與系統決定一對齊分數之1)值之多個估计。依據本發明之一種可較佳地應用於快速決定由一杳珣序列與一樣板序列之對齊所產生之一對齊分數X何時在統匕计上係不重要之方法包含以下步驟：丨）決定一臨限p值， ,2)决疋對齊分數又之卩值之一第一估計，ρ(χ|ΚΝ,，λ(」)0 ; y 將ρ(χ|κΝ/，娜）與π進行比較；及4)若ρ(χ|κ^ 疋原始對齊分數x在統計上係不重要的，否則決定對齊分數在、、充冲上可此係或可能不係不重要的。依據本發明之另— 種用於快速決定一原始對齊分數\是否在統計上係不重要 =方法包含以下步驟：υ決定—臨限p值，pth; 2)決定對齊 ^ it X ^ p ^ ^ f ^ ? ) ； 3) ^

〇λ91\91145 DOC -10- 200419423 ρ(χ|κ(λ(」)+Ν/ΓΝ/，λ(」)+Ν/)與 p(x|K(x(jrN/rN/AQrN/)>pth, 重要的’否則決定原始係不重要的。 4)若上係不可能不

Pth 、& . 進行比較；及則決定原始對齊分數X在統計對齊分數X在統計上可能係或依據本發明之該蓉古、土处 /專方去使用原始對齊分數Χ2ρ值之複個估计來反覆地決定义是 *钓I要的或不重要的。因而，依據本發明之另一種可田分V Wr、土 _L ^ 裡了用於快速決定由一查詢序列與一樣板序列之對齊所產生之一料赢八& 生之對齊分數X之統計重要性或不重要性之方法包含以下牛驟卜步驟· 1)決疋一臨限p值，pth ; 2)決始對齊分數X之P值之一笛 J.J, ^ , 、值之第一估計，Ρ(Χ|κΝ/，λω;,) ; 3)將 ρ(χ|κΝ/，λ(瓜）與Pth進行比較；4)若ρ水/機始對齊分數X之p值之一第二估計ρ(χ|、，λ(队），其中 N!，否則決定對齊分數χ在統計上係不重要的；5)重複步驟 3)與步驟4)直到決定原始對齊分數X之p值之一最後估計 U ; 6}將ρ(χμ〜，;I⑺與pth進行比較及7)若 $ Pth，則決定原始對齊分數X在統計上係重要的’否則決定原始對齊分數乂在統計上係不重要的。依據本發明之另一種用於決定一原始對齊分數χ在統計上係重要或不重要之方法包含以下步驟：丨）決定一臨限ρ 值’ Pth ; 2)決定原始對齊分數χ之ρ值之一第一估計， p(xlK(MjrN/)kA(j)w ; 3)將 ρ(χ|κ(λω+Ν/4，λ% 若ρ(χΙκ(λ(」)：Λ，λω+Ν/) > pih，則決定原始對齊分數\之ρ值之一第二估計P(x|K(Mj)HMj);:)，其中N2 ^Νι，否則決定對齊分數X在統計上係不重要的；5)重複步驟3)與4)直到決定原妒 O:\9I\91I45.DOC -11 - 200419423 對齊分數X之p值之一最後估計P(x即⑺_ )〜，心 P(+(A⑺A())l) - p〜要的，否則決定對齊分數X在統計上係不重要的。另一種用於快速決定一原始對齊分數之統計重要性或不重要性之方法包含以下步驟· 1)決定 >一臨限p值，P t h ; 2)争定原始對齊分數X之P值之一第一估計，ρ(χ|κ(λ(沉，义，; 3)將與 Pth 進行比較；4)若 ρ(χ|κ(λ(」)[ >Pth，則決定原始對齊分數x之p值之一第二估計 Ρ(χ|κ(λ0+Ν:)Ν2，λ〇)[2)，其中NfN!，否則決定原始對齊分數在統計上係重要的，· 5)將進行比較，·幻若 ρ〇ψ^ω+Ν，ΓΝ，，λω;ι) s ，則決定原始對齊分數乂之p值之一第三估計ρ(χ|κ⑽，其中N3，，否則決定原始對齊分 =、，ST上係不重要的；7)重複步驟3)至6)直到決定原始背为數X之p值之一最後估計ρ(χ尤( ’、σ vyV九，又⑴、）；8) 巾叫(HW)。與Pth進行比較；及9 j(U<p ’則決定原始對齊分數X在統計係重要的，否則決定原始對齊分數χ係不重要的。除依據本發明之此等方法外，本發明乂 ^ 、力一万面係、一程式化用以執行依據本發明之方法之電腦 ’、【實施方式】 ' 依據本發明之方法所主張發明部分係基於以下觀察. 1)若 λ2$λ丨且 κ2^κ丨，則 ρ(χ|κ”λ，）- ’若一

〇 \91\9I145.DOC -12- K::數二在統計上係不重要的_即若對於一組特定的、與心二1)，其ρ值超過某—臨限值-則對於第二組 1 f么，χ在統計上將不重要(〜叫认)。 c / 刀佈係正規的。在連續分數之情形下，其標準偏差（標準誤差）可表示成1其具有—平均值！。對於有限對背分數之情形，其標準誤差可表示y λϋ其具有一平均值1。 3)^之分佈係、正規的，具有—平均值…其標準偏差可表示成〇 4)觀察2進一 ^之標準誤差，的0 步表明，對於不等式指派該不等式係有 "，其中口係八 true 效之一機率係真實可能 5)對於連續分數之情形 Λ W)N〈Xtrue〈入⑽，其中 λ(」·)[ = —·^且入(力+=一 λ 允<了一<1 + 7σ可重新寫成八true 6)類似地，觀察3進一乎主口口皮 v表明，對於不等式 ]-ίσ<-—+ ，其中σ係-之與唯—口、， … K- ke夂^準誤至，指派該不等式係 true 且有效之一機率係可能的。 7)對於連續對齊分數之情形 Κ(λ〇*)；)- <^<^〇)；)；，其 jCJ<^<7 + jcJ可重新寫成中 κ(λ〇·);ΓΝ VNmn O:\9I\91I45.DOC • 13 - 1 + - 200419423 ι+ je VNmr 上述觀察為依據本發明之快速對 -或多個基礎。由於p(柄與κ成指數關係二化方法充當指數關係，故對於雖,)之_精確；;叫成雙重比™計更重要。為了表示簡單，此; nr輪廓對齊所產生之連續對齊分數。熟習此：者-般應明白序列-序列對齊與輪廓_輪廓對齊之間性。本發明完全可應用於兩者而沒有限制。 a 圖丄中所示依據本發明可較佳地用於快速決定由—㈣序列與-樣板序列之對齊所產生之一對齊分數\之統計重要性或不重要性之方法包含以下步驟· υ決定i—臨限P 值，Pth ; 2)決定3原始對齊分數X2P值之一第一估 ; 3)將 Ρ(χ|κΝ”λ(队）與 pth 進行比較 5 ;句若 P(x|KN/A(j)k)SPth，則決定9原始對齊分數乂之^值之一第一^ 計P(x|KN，CTNJ，其中，否則決定7對齊分數乂在統計」係不重要的；5)重複15步驟3)與4)直到決定原始對齊分數之p值之一最後估計p(xl〜，吣)+0 ; 6)將P(伞心^ 進行比較17 ;及7)若Ρ(χ|κΝ‘λω;^ $ 2卜則決定原始對奪分數X在統計上係重要的，否則丨9決定原始對齊分數X在僉計上係不重要的。雖然熟習此項技術者理所當然應明白，一般言之，KN/與九(沉,可表示成κΝ/κ與λϋ); λ，但是為了表六簡單，Ν/，κ=Ν/λ係不必要的，故將說明Νπ=Ν/λ=]^之情形。決定一臨限ρ值Pth O:\9I\91145.DOC -14- 依據本發明並在圖1中所說明之一方法中之一第一步驟i 為一對齊分數X決定一臨限P值，pth。一般言之，臨限她 ]、時：對齊分數必須增大以視為在統計上係有意義的。因、，σ基於特疋5旬問所需之對齊敏感度與經篩選之特定資料庫之大小來選擇臨限？值。例如，若一生物資訊學家2 ”趣於相對於！，()()()，〇⑼個樣板序列之—資料庫來篩選一= 珣序列以偵測與由一對齊分數χ所定義之查詢序列遙遠相關之所有此等序列，一臨限？值1〇_6將對應於預期值（「〇值」） P資料庫中之一樣板序列將產生與至少χ之查詢序列之 u 一〜^扭判應於密卡相關之序列、1〇-3與1〇之間之e值對應於遙遠相關或模糊^ 列且大於10之e值對應於不相關序列。因而，用於偵測密七相關序列之範例性臨限？值可包括之此等值，其中表示一資料庫中樣板序列之數目。用於偵測遙遠相關序列之範例性臨限P值可包括—之此等值。

Z Z 決定P值之一第一估計Ρ(χ|ΚΝ,，λϋ); ) 一第二步驟3使用應用於一第一組Ni個島之島方法為一對齊分數X決定一第一 p值以+〜从沉,）。此第二步驟進一步視基於Xtrue $ λ(』)1之統計概度選擇而定。由於」二之半峰全 λίπιβ 幅值隨j增加而增加，故λ^<λϋ)+Ν/概度隨j增加而增加。例如，尸3，存在λ(%<λ加6<λ(枞之一99.8%的機率。對於更高的J值，Ρ值估計之精確性進一步增加。可使用等式4決定Κ O:\91\91I45.DOC -15 - 200419423 在對齊分數X之P值之 ..^ ln 第一估计中所使用島之數目N|通常靶圍在100至1000之p & 一 Ρ(χ|κ 間，但乾圍可高達5,000。由於 (Ν/ ’入(j)N )充s第一漁淡哭田，、/二处CT丨上應波為用以識別在統計上係不舌要之對齊分數中的多個，故奢俘在π 文“地取小化所產生島之數目以便 I 貪源。一般言之，史密斯_沃特曼矩陣中島之數目通,視序列長度與得分方案而定。然而，假設查詢序列之典型序列長度及300個剩铨夂叫餘之母一樣板且進一步假設典蜇的肌BLAST間隙得分方案，可藉由小於ι〇個之序列隨機化二情形下藉由小於5個之序列隨機化產生。將？(^，(沉/)與？化進行比較 ^ f ^ ^ ^ PCxlK,,^)!. # tb |jt 〇 ^ ?ρ(χΚ>λα)； ) ρ則精由將查δ旬序列與第—樣板序列對齊所產生之原始對齊分數可認為在統計上不重要。決疋ρ值之-第二估計p(x|n) 若？水'，卿^9’則不存在足夠資訊用以決定是否且因而不足以決定查詢序列與第一樣板序列之間之原始對齊分數是否可看作在統計上不重要而忽視。因而，:第四步驟9為一較大的第二組化個島決定 (N: C0N:)饭αχρ值之第—與第二估計係用於過濾統計上不重要之對齊分數，範圍通常自至3500個島，但是範圍可高達7,0〇〇。重複步驟3)與4)直到決定味第五步驟重複15第三與第四步驟整數次。因而，若叩^’(〇 gP ’其中3，則仍不存在足夠資訊用以決

O:\91\9U45.DOC -16- 200419423 定是否p(x|^^/nJ>pth。下一步驟為更定POclK W、甘I 之第個島決及第V'1、、Νη>Νη·!。在下-步驟巾，使用血第：及第四步驟中所述比較方案相同之比，、弟- 盘 Pth 進杆 fc卜 # 舌、-L Ρ^Χ|ΚΝη^λ0)Νη) 之Ρ值之最後估計P(x|K W 原始對齊分數χ 之最後估計使得轉;/) π 對齊分數叫值 I %’ 。由於丄中的標準誤差隨7/ν^減小，對於Ν=9 _ λ"β 、钽一乂乂咖。因而若對Ρ值進订η個估計，則每一步騾中所考慮島之數 1 〇〇(對於w、、π丄乾圍將從大約蛛Γ ，000或更多（對於最後估計、力U，（〇)。對於可由所主張方法採用之ρ值估計之數目可由所主張方法採用之。值估計之數目視可可尸 f料庫之大小及搜尋之敏感度而^。通常算資Ή = p值估計。但是，假定具有足夠的計 t.....讀千個料° #料庫巾已_選相之多數將與查詢序列不g 士 M d J <夕數將之p值之第—估竹亦\上有意義之對齊，且原始對齊分數算費用^二有用的濾波器用於以較低的計、、逮决疋許多此類統計上不重要之分數。此點表明依據本發明$ $ 士、t — ^月之另—方法。藉由執行步驟2至4，決逮決疋一原始對齊分數在統計上是否係不、 —般言之，可重複步驟2至3複數次，龙中從一 =數目（相對於？值之先前估計）之島中決定p值之每一估 ”亦遵循—點’即非線性增加N在計算上更有效，因而最

〇A9|^Il45.D〇C -17- 初少數p值估計使用小於、、力3,500個島。儘管在僅有兩個p 值估計得以計算之愔开彡 ,價形下，但可從甚至5000個島中決定第一估汁 ρ^Κν,αο·);,)。不將吵1心^(1)與？化進行比較一最後步驟1 7使用盥筮一半州一弟二步驟5中所採用之比較規則相 ° ^ th ^ ^ P(x|KNfin^(j)；fiJ i% Pth it th I5C 〇 0 ft ^ p(xlK^AG)Nfinal) m可認為原㈣齊分數 21，否則認為原始對齊分數又在統計上不重要19。範例1 圖2中所示以下範例將說明如何應用依據本發明圖1中所不方法以決定將-查詢序列與包含i，_，Q_個樣板序列之車乂大資料庫中每一樣板序列對齊所產生之此等原始對齊分數是否在統計上係重要的或不重要的而不使用查找表。假設藉由將查詢序列與一第一樣板序列對齊來決定一原始對月刀數X。進一步假設在第一步驟25中將臨限p值選為1〇·6 使得所報告之已正規化對齊分數對於遙遠相關樣板序列係敏感的。一第二步驟27決定原始對齊分數X之p值之一第一估計 Ρ(χ|κ·二έ，λ⑺；=2.以，對於N=l〇〇個島且j = 5。因為藉由產生 1 00個島所施加之計算負載受限制，最初選擇N= 100。假設採用典型的PSLBLAST間隙得分方案，可藉由小於1〇個之序列隨機化或許多情形下藉由小於5個之序列隨機化產生 100個島。一第三步驟29將ρ(χ|κΐ()()=元2(5)^=2.(^)與1〇-6進行比較。若3 1 Ρ(χΚ· =έ，λ(54 =2.冰> 1 〇_6，則查詢序列與第一樣 O:\9I\9H45 DOC -18- 200419423 板序列^之原始對齊分數可看作在統計上不重要而忽視且可計算查詢序列與第二樣板序列之原始對齊分數。因而採用極少數的序列隨機化且因而計算負載最小，即使原始對齊分數之p值之一第一估計（與觀察i組合）亦可用以快速決定一原始對齊分數在統計上是否係不重要的，其具有 <<<1%之一誤差率。若/>(ΧΑ。。=ΚΑ(5)；〇。S 1〇-6，則一第四步驟決定原始對齊分數乂之p值之一第二估計尸= tA(%。。=uii)，對於規則相同之比較規則將Ρ(χ&5。。 N=2500且j = 5。一第五步驟35使用與步驟4中所使用之比較 =之；1(5)25。()=1.11乂）與1〇-6進行比較。因而，若Ρ(χ|尺25Q。=尤，又(5)2+5。。= U1>^ $ ! 〇-6，則一第六步驟Μ 決定原始對齊分數X之Ρ值之一第三估計 Ρ(χ尤9，_ —之又(5)9，_ »U ’對於ν=9,000且j = 5，否則認為原妒對齊分數在統計上不重要。一第七步驟41將户(x尤9,〇〇〇 =之义(5) )與1 (Γ6進行比較。若4 5 P{x K9 Q00 = Κ, /1(5)9 000 « Xtrue )^10 ，則可認為原始對齊分數在統古十上重要，若43 P(x[9Q。。=i；，；L(5)_ »〇> 1 〇-6，則可認為原始對齊分數在統計上不重要。依據本發明並視基於共同變化之λ與K對ρ值之估計而定之另一正規化方法可使用觀察4與6而進行。由於對於此等情形’原始對齊分數X之ρ值之估計視λ與Κ都為變數，故庶將Ρ(χ|κ，λ)重新寫成。圖3中所示此方法包含以下步驟·· 1)決定51—臨限ρ值，Pth ; 2)決定53原始對齊分數 X之P值之一第一估計Ρ(ψφΙ(瓜W，又(瓜〕；乃將 O:\9I\91145 DOC -19- 200419423 Ρ(χ|κ(λ0·ΓΝ/ΓΝ/，λ(」);/)與進行比較 55 ; 4)若 59 P(x|a：(/L⑺％⑺乂）S p ，則決定原始對齊分數X之p值之一第二估計 ρ(χ|κ(λ〇’ΓΝ:)-Ν:，λ〇·);:)，其中 N2$Ni，否則 57決定對齊分數X在統汁上係不重要的；5)重複61步驟3)與4)直到決定原始對齊分數X之p值之-最後估計Ρ(χ|κ(λϋ);」^(队」… Ρ(χ|κ(λ(υΝω，λ(υ 與 Ρ 進行比較 67 ;及 7)若 71 P(x|K(X(jH，x(j)N J $ Ρ ’則決定原始對齊分數X在統計上係重要的，否則69決定原始對齊分數乂在統計上係不重要的。雖然熟習此項技術者理所當然應明白，一般言之κ(λϋ瓜與籲 λω;可表示成Κ_)〜與λ〇);/λ，但是為了表示簡單，化κ =Ν/λ 係不必要的，故將說明Νλκ =Ν/λ =乂之情形。範例2 圖4中所說明以下範例將基於觀察4與6中之不等式及圖3 中所示來說明如何應用所主張之方法以決定藉由將一查詢序列與一較大的樣板序列資料庫中每一樣板序列對齊所產生之原始對齊分數之統計重要性或不重要性。再次假設藉_ 由將查询序列與一第一樣板序列對齊來決定一原始對齊分“ 數X且樣板資料庫包含1，〇〇〇,〇〇〇個序列。進一步假設在第一一步驟75中將臨限ρ值選為1〇-6使得所報告之已正規化對齊分數對於遙遠相關樣板序列係敏感的。一第二步驟77決定原始對齊分數X之ρ值之一第一估計ρ(χ|κ(λ(5)^)·，λ(5ω，對於 Ν—100個島且卜5。一第三步驟79將ρ^κ(λ⑺^)_，吣)二）與1〇_6 進行比較。若8丨Ρ(χ|κ(λ(5ω湖，λ〇5)二)> 丨〇_6，則查詢序列與第一樣板序列之間之原始對齊分數可看作在統計上不重要而

O:\91\91145.DOC -20- 200419423 忽視且可計算查詢序列與第二樣板序列之原始對齊分數。因而採用極少數的序列隨機化且因而計算負載最小，原始對齊分數之p值之一第一估計（與觀察丨組合）亦可用P =

快速決定一原始對齊分數是否在統計上係不重要的，其具有<<<1%之一誤差率。 /、A 右83 ρ(χ|κ(λ(5):)_λ(5):) $丨〇-6 ’則一第四步驟決定原始對齊分數X之P值之一第二估計P(x|K(H，D ’對°於 .2500且卜5。一第五步驟85使用與步驟4中所使用之比較規則相同之比較規則將P(x|K(Uw，D與1〇·6進行比車口而若 ρ(χ|κ(λ(5)·)纖,λ〇5)2+00)$ 1〇.6，則一第六步驟決 =原始對齊分數X之Ρ值之一第三（最後）估計啊入⑺峡}華’入⑻’卿；）’對於如1〇，()〇()且j = ：5。否則π亨為原始對齊分數X在統計上係不重要的。—第七步驟^將 Ρ(χ|Κ(λ(5)；·_》_，λ⑼_)與 1〇-6 進行比較。4 95 ! 〇-6，則認為原始對齊分數在統計上係重要的，否則93認為原始對齊分數在統計上係不重要的。對於可由圖3至4所說明之方法採用之原始對齊分數之p =計之數目沒有时限制。可採用之p值估計之數目視資寻之大小、所需敏感度及可用的計算資源而定。通用兩個至大約十個p值估計具有足夠的 ^ 彳貝科庫巾已轉相之多數、查為序列不具有統計上有意義之對齊，且原始對齊分呼曾1值之第一估计可充當一有用的濾、波器用於以較低的 5异、用快速決定許多此類統計上不重要之分數。

〇：\9|\91 !45 DOC -21 - 200419423 此點表明依據本發明之另—方法。藉由執行步驟2至4，即由阶|κ(λ(」);/)-Ν/，λϋ·ΓΝ/)決定原始對齊分數之p值之估計並將此估計與一臨限P值進行比較，可快速決定是否一原始對齊分數在統計上係不重要的。更一般言之，可重複步驟2至3 複數次，其中從一更大數目（相對於？值之先前估計）之島中決定P值之每一估計。其亦遵循一點，即非線性增加^^在計算上更有效，因而最初少數的P值估計使用小於大約3,5〇〇個島。儘管在僅有兩個p值估汁得以計异之情形下，但可從甚至5〇〇〇個島中決定第一估計 ρ(χ|κ(λϋ·ΓΝ/)-Ν/，λ(Α)。觀察4與6中之不專式允許圖5中所示用於快速決定一原始對齊分數之統計不重要性/重要性之其他方法，其包含以下步驟：1)決定101—臨限Ρ值，pth ; 2)決定1〇3原始對齊分數X之P值之一第一估計ρ(χ|κ(λω;^，λ(仏）；3)將 P(x|K(^(j)Hx(j)k)與 pth 進行比較 1〇5 ; 4)若 109 ’則決定原始對齊分數X之ρ值之一第二估計Ρ〇ί|κ<ΧΤΝ:)〜，λ〇χ，），其中N2=Ni，否則107決定原始對齊分數在統計上係重要的；5)將Ρ(χ|κ(λ〇·)»〇·)+Ν:)與pth進行比較 111 ; 6)若 115 P(x|K(xcjrN:)；vx〇yN7)$pih，則決定原始對齊分數X之P值之一第三估計，其中NgNi，否則11 3決定原始對齊分數在統計上係不重要的；7)重複1 i 7 步驟3)至6)直到決定原始對齊分數X之ρ值之一最後估計 ρ(χΙκ(λ(ι又^ Π9;及9)若121Ρ(Χ|Κ㈤)則決定原始對齊 O:\91\91145.DOC -22- 200419423 分數X在統計上係重要的，否則123決定原始對齊分數χ係不重要的。雖然熟習此項技術者理所當然應明白，一般古之 κ(λ(職與灿；可表示成尤與但是為了表示簡單，=NU係不必要的，故將在以下範例中說明，κ /,λ ^ Ny 之情形。範例3 圖6中所不以下範例將顯示如何應用以上剛剛詳細說明並在圖5中圖解說明之方法以決定藉由將一查詢序列與具有1，000,000個樣板序列之一資料庫對齊所產生之原始對齊分數之統計重要性或不重要性。再次假設藉由將查詢序列與一第一樣板序列對齊來決定一原始對齊分數χ。進—步假設在一第一步驟141中將臨限ρ值選為pth =1〇·6。一第二步驟143決定原始對齊分數X之p值之一第_估計 ⑷:。。):。。，乂(4)「。〇)，對於N=100個島且 j=4。一第三步驟 145 將Ρ(χ|κ(λ⑷·)·λ⑷⑽）與1〇 6進行比較。若Mg ρ(χ|【μ⑷;0。)1+。。，4(4)1。())>1〇6’則一第四步驟計算原始對齊分數乂之Ρ值之一第二估計P(+：(A4);〇g)_W4);〇q)，其對於與第二步驟 t ^ ^ ^ [S] ^N=l〇〇^ ft j. j=4〇 ^ 147 S 10 6 ’則可認為原始對齊分數在統計上係重要的且可計算查詢序列與第二樣板序列之原始對齊分數。一第五步驟1 $丄將 ρ(χ|κ(λ^);)·，λ(4)“）與 ΙΟ.6 進行比較。若 153 Ρ(χ|κ(λ(〇卿)·，λ(〇·)>1〇 6 ’則可認為查詢序列與第一樣板序列

之間之原始對齊分數在統計上不重要。若15 5 Ρ(χ|κ(λ⑷；丄,，λ⑷;J $ 1 0 6 ’則一第六步驟計算原始對齊分數X O:\91\91145.DOC -23 - 200419423 之p值之一第三估計Ρ(χ|κ(λ⑷;_);_，λ⑷厕），對於n=3000個島且 j = 4 〇一第七步驟157將Ρ(χ|κ(λ(%_);_，λ⑷厕）與ΙΟ·6進行比較。若 159 Ρ(χ|κ(λ(4)蕭))·α,λ(4)遐$ 1 0 ’則可認為查詢序列與第一樣板序列之間之原始對齊分數在統計上係重要的且可計算杳詢序列與弟二樣板序列之原始對齊分數。右161户(χ|火(义(4)3_)3_,义⑷·。）〉1 〇 ’則一第八步驟決定原始對齊分數X之P值之一第四估計ρ(χ|κ(λ⑷;卿)麵，。一第九步驟1 63將Ρ(χ|κ(λ⑷厕)删，人⑷丨卿）與1〇6進行比較。若167 Ρ(χ|κ(λ⑷蕭)3_,λ⑷3_) $ 1 〇 6 ’貝一第十步驟決定對齊分數乂之p 值之一第五（最後）估計？(水(_;_)_，_;，卿），對於 N=10,000且j=4。若 165P(X|KW%_)厕，λ⑷；_)>1〇·6，則認為原始對齊分數X在統計上係不重要的。由於 Ν=10,000 Ρ(χ|Κ(λ(¥) ιο〇〇〇) +l〇〇〇〇 ? λ(^) l〇〇〇〇) ρ(χΙκ(λ(^_)零，哪，_) ’故 ρ(χ|κ(λ ⑷；，_)70,_，λ⑷；-), P(X|‘_D。一第十一步驟169將與10 6進行比較。若173 Ρ(χ|κ(λ(υ_’χ⑷丨_) $ 1 〇·6 ’則藉由將查詢序列與第一樣板序列對齊所產生之原始對齊分數可認為在統計上係重要的，否則171可認為原始對齊分數在統計上不重要且可計算查詢序列與第二樣板序列之原始對齊分數。對於可由圖5至6所說明之方法採用之原始對齊分數之？值估計之數目沒有固有限制。可由所主張方法採用之ρ值估計之=目視可用的計算資源、資料庫之大小及搜尋之敏感度而定。通常可採用兩個至大約十個ρ值估計。但是，假定

O:\91\91145.DOC -24- 200419423 具有足夠的計算資源可決定數千序列之多數將與查詢序列不具有 ^庫令已㈣原始對齊分數之P值之第一估計可充告有;、義之對齊’且較低的計算費-速吻多；此點表明依據本發明之另一方法。即由吻卿;，，简）決定原㈣齊分；^^驟2至4，月刀数之P值之估計並將此估計與-臨限P值進行比較， ^ -J. U B . 六、原始對齊分數 ==否係重要的。更—般言之，可重複步驟…複從一更大數目€相對於P值之先前估計）之島中決疋P值之每一估計。類似地亦表明依據本發明之另一方法。猎由執行步驟3至5,即由痛決定原始對齊分數之Ρ值之估計絲此估計與—臨限ρ值進行比較，可快逮決定-原始對齊分數在統計上是否係不重要的。更一般言之，可重複步驟3至5複數次，其中從-更大數目(相對於Ρ值之先前估計）之島中決定ρ值之每—估計。其亦遵循一點，即非線性增加1^在計算上更有效，因而最初少數的ρ值估計使用小於大約3,5〇〇個之島。 :在僅有兩個ρ值估计得以計算之情形下，但可從甚至 5000個島中決定第—估計畔卿乂观,）。依據本發明之系統一般吕之，如圖7所示，依據本發明之一系統175包含一 ^ 器丨77 ' 一圮憶體179、一輸入裝置181、一輸出裝置斗對作業系統之程式設計1 8 5、用於決定序列對齊

O:\9I\91145.DOC -25 - 200419423 分數之程式設計1 87、用於儲存並擷取複數個序列與對齊分數之程式設計19 3及針對依據本發明之方法之程式設計 1 8 9。依據本發明之系統亦可視需要包含用於與另一裝置形成網路之一系統1 9 1。處理為17 7可包括一或多個微處理器、場可程式化邏輯陣列或一或多個特定應用積體電路。範例性處理器包括英特爾公司（Intel Corp·)的奔騰系列處理器（加利福尼亞州的聖塔克萊拉）、摩托羅拉公司（Motorola Corp.)的powerPC處理器（伊利謹伊州的蕭慕堡）、梅普思科技有限公司（MIps Technologies Inc·)的MIP處理器(加利福尼亞州的山景城）或賽靈思有限公司（Xilinx Inc·)的場可程式化邏輯陣列之 Vertex系列（加利福尼亞州的聖荷西）。記憶體179包括任何用於儲存數位資訊之電子、磁性或光學基媒體或此類媒體之一組合。記憶體之範例類型包括隨機存取記憶體、電子可程式化唯讀記憶體、快閃記憶體、磁碟機與磁帶機及光碟機。記憶體儲存針對依據本發明之方法之程式設計。輸入裝置181可包括鍵盤與滑鼠或觸控螢幕/輸入板或其某一組合。輪出裝置183可包括一或多個視覺顯示器及或印表機。視覺顯示器可基於此項技術中所熟知之任何監視器技術，立包括陰極射線管基監視器/投影機、電漿基監視器、液晶顯不益基監視H、數位微鏡裝置基投影機或光閥基投影機。針對作業系統之程式設計185包含用於控制處理器、記憶〇 \91\9ll45 〇〇c -26- 200419423 體、輸入裝置與輸出裝置之間之資料流之機器碼。範例性作業系統包括微軟公司（Microsoft Corp)的Windows與 NT(華盛頓的雷德蒙）、昇陽有限公司（sun Micr0SyStein inc.) 的Solaris作業系統（加利福尼亞州的帕洛阿圖）、紅帽子公司 (Red Hat Corp·)的Linux版本（北卡羅萊納州的Durham)及 Palm公司（paim c〇rp·)的palm OS(加利福尼亞州的苗必達）。用於決定序列對齊分數之程式設計丨87包含用於決定序

列對齊分數之機器碼且可基於BLAST、PSI-BLAST或HMM 〆貝v去。參見生物資訊上由Baxevanis，A.、Ouellette，B.F. 所著之基因與蛋白質分析之應用指南（wiley imerscience， 2001) 〇針對依據本發明之方法之程式設計丨89包含用於執行依據本發明之方法之機器碼。網路系統19 1包含允許依據本發明之系統與另一裝置進行電子通信之硬體與軟體。範例性網路方案可基於透過任何媒體傳輸之封包，其包括乙太網路10/1000、電機電子工程師學會（ΙΕΕΕ)8〇2·11χ、IEEE 1394、xDSL、藍芽或任何其他美國國家標準學會（ANSI)認可之標準。用於儲存並擷取複數個序列與對齊分數之程式設計193 包括關係與物件導向資料庫例如甲骨文公司（Oracle Corp〇的9ι(加利福尼亞州的紅木城）、國際商用機器（Imernati〇nal

Business Machine)的 DB2(紐約的 Armonk)、微軟公司 (MlCros〇ft c〇rp·)的Access(華盛頓的雷德蒙）及Versant公司

O:\9l\91145.DOC -27- 200419423 (Versant’s (：〇”·>々乂以以加開發者程式套件6 〇(加利福尼亞州的弗瑞蒙特）。若對齊計算與序列係作為平坦檔案儲存，則用於儲存並擷取對齊計算之程式設計亦包括作業系統。依據本發明之系統可基於已程式化用以執行依據本發明之方法之個人電腦（PC)與網路伺服器。一適合的伺服器與硬體組態係企業類奔騰基伺服器，#包含具有丨gb隨機存取記憶體之一作業系統例如微軟的Ντ、昇陽的s〇ia岀或紅帽子的Lmux版本、100GB儲存器、一企業類資料庫、支援 tcp/ip、一線路區域網路通信卡例如1〇/1〇〇之一乙太網路卡或一高速的網際網路連接例如企業丁1/E1線路或\〇乩線路，企業資料庫包含複數個序列、序列對齊得分軟體例如 PSI-BLAST及針對依據本發明之方法之程式設計。以上所列儲存器及記憶體要求並非意欲表示最小的硬體組態，相反其表示歸檔時間可容易地從供應商購得之一典型伺服器系統。此類健器可容易地從德爾公司（Dell，Inc)(德克薩斯州的奥斯、;丁）或惠普公司（HewlettPackard，Inc )(加利福尼亞州的帕洛阿圖）購得，其具有除企業資料庫、PSI_BLAS 丁源碼及針對依據本發明《方法t程式設計《外的所有特徵。PSI-BLAST源碼可免費從 <紙卿減nlmnih g〇v/>處下載亚女I到企業伺服器上。企業資料庫可從甲骨文公司或國際商用機器有限公司購得。適a的桌上型pc與硬體組態係一奔騰基桌上型電腦，其包含至少128 MB的隨機存取記憶體、1〇 GB儲存器、一線路區域網路通信卡例如10/100之一乙太網路卡或一高速

O:\9I\9I145 D0C -28- 的網際網路連接 TCP/IP網頁_覽」/企業則1線路或xDSL線路、一 Explorer)、"例如微軟的網際網路探險家⑽⑽et 數個序列、序列對/1如微軟的Aeeess，該資料庫包含複 β仔分軟體例如PSI-BLAST及針對依據本發明之方法之程式_ 憶體要求僅意欲表再次說明，範例性儲存器及記

At ^不歸槽時間可容易地從供應商獲得之PC 組悲。該等要求並非咅於主一 n 、 F心、奴表不隶小組態。此類PC可容易地從戴爾公司或東並八3 _ 〜曰A y (加利福尼亞州的帕洛阿圖）購得，其 :有矛、SI BLAST軟體及針對依據本發明之蛋白質分類方弋又汁之外的所有特徵。PSI-BLAST源碼可免費從 URL· www.ncbLnim.nih.g〇v/>處下載並安裝到桌上型％上0 仏&已參考車乂佳具體實施例與特定範例說明本發明，但热白此項技術者應明白，本發明之許多修改與調整係可能的而不月離本發明之精神與範嘴。因而應清楚地明白，僅藉由範例方式進行此說明且說明並非限制以下所述本發明之範缚。【圖式簡單說明】圖1說明依據本發明用於快速決定藉由將一第一序列與一第二序列對齊所產生之一原始對齊分數之統計重要性或不重要性之一方法。圖2说明圖1所述方法之一特定實施方荦。圖3說明依據本發明用於快速決定藉由將一第一序列與一第二序列對齊所產生之一原始對齊分數之統計重要性或 O:\9l\91145.DOC -29- 200419423 不重要性之另一方法。圖4說明圖3所述方法之一特定實施方案。圖5說明依據本發明用於快速決定藉由將一第一序列與一第二序列對齊所產生之一原始對齊分數之統計重要性或不重要性之另一方法。圖6說明圖5所述方法之一特定實施方案。圖7說明依據本發明之系統之一通用硬體架構。【圖式代表符號說明】 175 系統 177 處理器 179 記憶體 181 輸入裝置 183 輸出裝置 185 針對一作業系統之程式設計 187 用於決定序列對齊分數之程式設計 189 針對依據本發明之方法之程式設計 191 與另一裝置形成網路之系統 193 用於儲存並擷取複數個序列與對齊分數之程式

O:\9I\91145.DOC -30-

Claims

200419423 拾、申請專利範圍： 1· -種用於決定從-第-序列與—第二序列之對齊中所決定之-對齊分數X是否在統計上係不重要之方法，其包含以下步驟： a·決定一臨限p值，pth ; b·使用該島方法決定該對齊分數义之^值之一第 ρ(χ|κ〜，λ(4)，其中κΝ;κ係使用Νι κ個島決定，使用Nu個島決定且j-3 ; c.將ρ(χ|κΝ/κ，λ(>τΝ/λ)與0進行比較；及一估計 λ(4係 d. 若户(Ά.);」>Ρίΐ1，則決定該對齊分數在統計上係不重要的，否則決定該對齊分數在統計上可能係、或可能不係不重要的。 2·如申請專利範圍第1項之方法，其中 1，Κ 於5000 〇 Nu每一個係小 3·如申請專利範圍第1項之方法，其中N 於3000 〇每一個係小 4.如申請專利範圍第！項之方法，其中Νικ 於 1000 〇每一個係小如申請專利範圍第i項之方法，其 i，κ 於 500 〇心每—個係小 0. :種用於決m-序列與—第二序列之對齊定之一對齊分數义在統計上係重要或包含以下步驟：重要之方法’ a· 決定一臨限p值，pth ; O:\9I\91145.DOC 200419423 b.使用該島方法決定該對分 ^ ρ(χκ λ(\ν \甘+ 义之？值之一弟一估計 ρ(χκΝ/κ，λ(」)Ν λ)，其中 & νλκ糸使用Nl K個島決定，λ(^係使用Nu個島決定且; Χ，、 c. d. 將P(xKN,KA(j);J與pth進行比較；若 ρ(χκΝ 人(沉） κ J — 則使用该島方法決定該對齊分數X之P值之一第二任。十 P(xlK\KA(j); j，其中 κΝ κ 係使用^^ 9000個島決定，Κ系使用^_0個島決定且⑷，否則決定該對齊分數X在統計上係不重要的； e. f. 將戶與Pth進行比較；及右SP h，貝u決定該對齊分數在統計上係重要的’否則決定該對齊分數在統計上係不重要的。 7·如申請專利範圍第6項之方法，其中 π…、γ n/k，nu母一個係小於 5000 〇其中Nak，Nu每一個係小 /、中ΝΛΚ，ΝΛλ每—個係小其中ΝΛΚ，Ν/λ每一個係小 8·如申請專利範圍第6項之方法 3000 〇 9 ·如申睛專利範圍第6項之方法 1000 〇 1〇·如申凊專利範圍第6項之方法 5 0 〇〇 :種用於決定從一第一序列與一第二序列之對齊中疋之一對齊分數乂在統計上係重要或係 ^ , 夏要之方法包含以下步驟·· a·決定一臨限p值，pth ; O:\9l\9U45 D〇C 200419423 b·使用該島方法決定該對齊分數X2p值之一第一估計 Ρ(χ|κΝ/κ，λ〇)+Ν/λ) ’其中ΚΝ/κ係使用Ν/κ個島決定，λ(」)^係使用Nu個島決定且j - 3 ; c·將？(+^別);/」與？化進行比較； d.若Ρ(χ|κΝ/κ，λ〇;/λ) $ Pth，則使用該島方法決定該對齊分數X之p值之一第二估計Ρ(χ|ΚΝ·κ，λϋ); j，其中係使用 Ν:，κ個島決定，λ(】)；^係使用Ν2，λ個島決定且〗$ 3，否則決定該對齊分數X在統計上係不重要的； C*重複步驟C)與d)直到使用該島方法決定該對齊分數之 p值之一最後估計作k⑽，犯U，其中係使用 >W^9000個島決定’ Λ(〇吏用D9〇〇〇個島決定且j$3 ; f.將ρ(χΙκι,κ，λωυ與Pth進行比較；及 g若P(x|KNfnaiK;(j)Nfmau) s p ，則決定該對齊分數义在統計上係重要的，否則決定該對齊分數乂在統計上係不重要的0 12. 如申請專利範圍第11項之方法，苴中乃/*·兵T N/K，NU母一個係小於 3 000 〇之方法，其中每一個係小於 13 ·如申請專利範圍第11項 1000 〇 14. 如申請專利範圍第11項 500 〇之方法’其中N/k，Nu每—個係小於 15. —種用於決定從一第—序序列之對齊中所決疋之一對齊分數X在統計上係重要或係文 < 方法，其 O:\91\9I145.DOC 200419423 包含以下步驟： a. 決定一臨限p值，pth ; x之P值之一第一估計個係使用川個島決定 b. 使用該島方法決定該對齊分數 P(X|KN/A(j);,)，其中\與⑷心每一且j-3 ; c. 將p(x|kn，ctN/)與進行比較； d. 若P(x|Kn,，W,)，則使用該島方法決定該對齊分數X 之p值之一第二估計味:，職），否則其中KN3與叫每 -個係使用n2個島決定續3,否則決定該對齊分數X 在統計上係不重要的； e. 重複步驟c)與d)直到使用該島方法決定該對齊分數之 ^ ^ ^ ^ ^ ^tf Ρ(χΙΚ-λ^> ^ ^ t ΚΝ^ λ〇)；^ _ 個係使用Nfmal^9000個島決定且jg3 ; f. 將ρ(χΙκ^，λωυ與pth進行比較；及則決疋該對齊分數x在統計上< 16. 17. 18. 重要的，否則決定該對齊分數\在統計上係不重要的如申請專利範圍第15項之方法，其中Νι係小於刪。如申請專利範圍第15項之方法，其中Νι係小於5〇〇。一種用於決定從-第—序列與—第二序列之對齊中所, 定之一對齊分數X是否在統計上係不重要之方法，皇勺/ 以下步驟：八匕 a.決定一臨限p值，pth ; b. 使用該島方法決定該對齊分數X之ρ值之一第一估計其中κ(λ(沉Λ，κ係使用νλκ個島決 O:\9I\91145.DOC -4- 200419423 定，ΜΧΤΝ/λ係使用ΝΛλ個島決定且」> 3 · c·將畔隊N/Ak⑽ 右 ρ(Ηκ(λω'Α，ωΝ/，λπ =係不重要的’否則決定該對齊分數在統計上可能係或可能不係不重要的。 19. 20. 21. 22. 23 如申請專利範圍第丨8項之方法，苴 '、中Ν/，κ，ΝΛλ每一個係小於 5000。如申請專利範圍第18項之方法，苴中 > 甲ΝΛΚ，Ν/λ母一個係小於 3000。如申請專利範圍第18項之方法，苴中 '、干ΝΛΚ，Ν/λ母—個係小於 1000。、如申請專利範圍第18項之方法，其中、Τ Ν/ κ，ΝΛλ母一個係小 500 〇 ' .:種用於決定從-第-序列與—第二序列之對齊中所決疋之一對齊分數X在統計上係重要或係不重要之方法，里包含以下步驟： / A a.決定一臨限p值，pth ; b·使用該島方法決定該對齊分數\之 ^ ^ 弟一估言十 ρ(χ|·);Α，λωί) ’ 其中 κ(λϋ);Ακ 係使用 μ 定，λ〇·);/λ係使用Ν/ λ個島決定且j - 3 ; C·將 ρ(χ|κ(λ(]υ/κ，λω;/λ)與 pth進行比較； d·若Ρ(χ|κ(λ〇·)[/λ)-Ν/κ，λαΤΝ/λ) s pth，則使用該島方法決定該對齊分數X之p值之一第二估計Ρ(χ|κ(λϋ)+Ν'λ)〜，心 κ(Μ」·)Ν:,λ)ΝΛΚ係使用Ν2，κ — 9000個島決定，仙+你处係使用 O:\91\91145.DOC 統計上係不重要的；否則決定該對齊分數X在 e ·將 P(x :κ(λωυ 〜，λ(」υ 與則决疋该對齊分數χ在統計 =係重要的，否則決定該對齊分數χ在統計上係不重要 24. 25. 26. 27· 28. 如申請專利範圍第23項之方法， 5,000 其中N/ K，NU每一個係小於如申請專利範圍㈣項之方法，其中N/為每 3000 個係小於如申請專利範圍第23項之方法，其中〜，〜每 1000 〇如申請專利範圍第23項之方法，豆 Τ以3以母~個係小於個係小於一種用於決定從一第一序列盘一 ^ h、弟一序列之對齊中所疋之一對齊分數\在統計上係重要或係不重要包含以下步驟： 4 ’ ,th a·決定一臨限p值，pt b.使用該島方法決定該對齊分數χ2ρ值之— ，其中κ(λ(^ 定，Μ」·ΓΝ/λ係使用Ν/ λ個島決定且j - 3 ; ’K ^ c·將 P(X|K(Mj)+Nj-N/K，MjrNj與 pth進行比較； d)右Ρ(χ|κ(λα)+Ν/λΓΝ/κ，λϋ); λ) g p〖h，則使用該島方法決定气齊分數X之P值之一第二估計p(x|K(m= J ΟΛ91\91145 DOC -6- 200419423 Κ(λ(υ:κ係使用N2，K個島決定，λ(」); λ係使用Ν2λ個島決定且j - 3，否則決定該對齊分數χ在統計上係不重要的； 29. 30. 31. 32. e) 重複步驟c)與d)直到使用該島方法決定該對齊分數χ 之Ρ值之一最後估計户⑺，乂⑺U，其中尤(又(/)〜,<^)〜^係使用1^111邮—9000個島決定，又(力[係使 final、入用乂心-9000個島決定且jg3 ; f) 將作丨似力二J%，犯與pth進行比較；及 g) 若P〇i：(；l()UJGU gpth,則決定該對齊分數χ 在統計上係重要的，否則決定該對齊分數乂在統計上係不重要的。如申請專利範圍第28項之方法，其中I'每—個係小於 3000 〇如申請專利範圍第28項 1000 〇如申請專利範圍第28項 500 〇之方法’其中νλκ， Nu每一個係小於之方法，其中Nr Ν/，λ 母一個係小於 — y w六不一吁夕^之審疋之對齊分數χ在統計上係重要或係不重包含以下步驟：所決，其 a•決定一臨限p值，pth ; b.使用該島方法決個島決定且j; 定該對齊分數X之P值其中Κ(λϋ)+Ν/Κ與人(乃;/每之一第一估計一個係使用％ O:\91\91145.DOC 200419423 c·將與進行比較； d·若 ) gh，則使㈣島 ^ 分數X之P值之一第二估計p(x|K(Mjd^+N:)，其中 Κ(λ(υ，與㈣每一個係使用N2個島決定且g 3，否則決疋该對齊分數X在統計上係不重要的； e) 重複步驟emd)直到使用該島方法歧該對齊分數χ 之Ρ值之一最後估計Ρ(ΧΙΚ⑽，，人(I)，其中 κ(λϋ·)+ΝΜ)ι與λϋ·)^每一個係使用Nfinag9〇〇〇個島決定且j-3 ; f) 將P(XIK⑽;與Pth進行比較；及 g) 若P(x|K(Mj);J-Nfmai’Mj);nJ各pth，則決定該對齊分數X在統計上係重要的，否則決定該對齊分數味統計上係不重要的。 33. 34. 35. 如申請專利範圍第30項之方法，其中Νι係小於職。如申請專利範圍第30項之方法，其中Νι係小於5〇〇。一種用於決定從一第一序列盘筮一汁幻14第一序列之對齊中所決定之一對齊分數X在統計上係重要或係不重要之方法，其包含以下步驟： /' /7ν b.使用該島方法決定該對齊分數χ2ρ值之—第一 _嶋,又，氣），其中系使用^個襄定，⑷)〜與λ队每一個係使用& λ 4固島決定且]g C·將P(xl尤(义⑺k)》,，，乂⑺〜）與Pth進行比較； — d·右畔(駡又，鄕iJ>pth，則使用該島方法決定該 O:\91\91I45.DOC 200419423 齊分數X之p值之一第二估計，其中 K(Mj)U'K係使用個島決定，λ(^係使用 Ν2，λ=ΝΛλ個島決定且3,否則決定該對齊分數χ在統計上係重要的； e. f. 將p(x尺⑻H 與pth進行比較；右p(x|尤μ(/);2丄2?乂⑺;」$ pth，則使用該島方法決定該 # # ^ x^p^t ^ ^ ^ tf ^ 中尤W);3,A);3，，係使用仏，1^9,〇〇〇個島決定，；^與 λ(^λ每一個係使用Nu g 9,000個島決定且J - 3，否則決定該對齊分數X在統計上係不重要的； g· h. 將P(x耶⑺〜)〜，;L(y’)〜）與p t h進行比較；及右A抑以h，則決定該對齊分數X在統計上係重要的’否則決定該對齊分數\在統計上要的。 36. 37. 38. 39. 40. 如申請專利範圍第35項之方法，其中小於5000 〇如申請專利範圍第3 5項 3000 〇如申請專利範圍第3 5項 1000 〇 Ν/，κ’Ν/ λ 每一個係之方法，其中nak，nu每一如申凊專利範圍第3 5項之方法 500。其中Ν/ κ,Ν/χ母— 個係小於個係小於個係小於 !π π厌定從一第一序列與一定之-對齊分數X在統計上係重要或::重 O:\91\9I145.DOC 200419423 包含以下步驟： a·決定一臨限p值，Pth ; b. c.d. 使用該島方法決定該對齊分數χ2ρ值之一第一估計 . ^ t κ{λϋγΝ{Λ %^ ^ Ni>Kii 定’ λ(_|·)Ν;λ與λ(_|·)1每一個係使用N以個島決定且j u ; 將作尤(乂())〜）1，义())^)與？化進行比較；若ρ(χ^μ(/^)+〜，Λω〜）>ρί[1，則使用該島方法決定該對 # f tt P(X|K(M^ , ^ t κ(λωυ〜係使用N2，K，1K個島決定，λ(ι係使用 Κ，λ =NU個島決定且j - 3，否則決定該對齊分數χ在統計上係重要的； e.f. 將阼即(1)1，叫);」與？化進行比較；若 ρ(χΙκ(λ(队凡，λ(^ # ^ x^p^i ^ ^ ^ t+ P(x|K^(j)；J；K?Mj)^ , ^ t Κ(λω+Ν」+Ν,，κ係使用n3，k個島決定，個係使用Ν,λ #島決定且j^3,否則決定該對齊分數 X在統計上係不重要的； g· h. 重複步驟e)至f)直到使㈣島方法決定該對齊分數乂之 p值之「最後估計p(xlK⑽灿w)，其中 (入(九{^)〜!11，1<：係使用]^111邮—90〇〇個島決定，盘+ — U、flnaJ,x /、λ(」)Ν-母一個係使用Nfma丨，λ - 9000個島決定且J - 3 ; 將 P(X|K_^人若 Ρ(ψ(λ(j)Nfi_ 丄⑽ κ，λ〇·)^ 統計上係重要的，否則決㈣對齊分數X在統計上係不 O:\91\91145.DOC -10- 200419423 重要的。 41. 42. 43. 44. 如申請專利範圍第4〇項之方法，其中N/K n卜母一個係小於3000 〇、如申請專利範圍第4〇項之方法，其中n ^ v，K，iNu母一個係小於1000。如申請專利範圍第40項u法，其中Ν/κ，Ν/λ每—個係 500 〇 ' 種用於決定從一第一序列與 — ——對齊中所決疋之一對齊分數义在統計上係重要或係不 ^ x 文 < 万法，复包含以下步驟： /、 a·決定一臨限p值，pth ; b•使用該島方法決定該對齊分數X之P值之—第— ρ(χΐκ(λϋ)+Ν’)+Ν"λ(〜）’其中κ(卿使用Ν1個島決定且j 2 3 ; c_ 將 Ρ(χΙΚ(λω^λ(：ίΓΝ/)與Pth進行比較； d. 若P(x_;A，^)>pth，則使用該島方法決定該對分數x之p值之—第二估計吻卿），其 Κ(λ〇ν，)Ν，％每一個係使用N尸Νι個島決定且⑷ 否則決定該對齊分數χ在統計上係重要的；~ e. 將 Ρ(Χ|Κ(λω^λϋ);)與 pth進行比較； f·若 Ρ(χ|Κ(λ(讥丄，，λω h ' 則使用该島方法決定該對分數X之P值之一 ^ •… 弟—估計户(伞(犯)；)；，乂队），其 K(Mj)Nj)N,、λ(]·)[鱼吣)Ni母一個係使用ν3個島決定且 3，否則決定該对赢八才月刀數χ在統計上係不重要的； O:\9I\91145.DOC -11 - 200419423 g·重複步驟e)至f)直到使用該島方法決 P值之一最後估計Ρ(χ|κ(λϋ)+ )+N f月刀:二 K(^J)NfiJNfinal ^ x(j)；finaiik λ〇·)-πη^ _ # ^ ^ ^ 9〇〇〇^ 島決定且j^3 ; h.將P(x|K(Mn，x(j)〇與pth進行比較；及 .右p(x|K_NfiM|)Nfi’(J)NfiJ “h，則決定該對齊分數χ在統計上係重要的’否則決定該對齊分數_統計上係不重要的。 45. 如申請專利範圍第44 H心万/安其中Νι係小於1000。 46. 如申請專利範圍第44項 47 ^ a <力/2:，其中％係小於5〇〇。一一種電腦系統，其包含： a•—輸入裝置； b•一輸出裝置； c· 一處理器； d· 一記憶體； e•針對一作業系統之程式設計； f. 用於決定序列對齊分數之程式設計； g. 用於館存並#貞取複數個序列與序列對齊分數之程式設計；及 ^針對如申請專利範圍第2項之方法之程式設計。 48· 一種電腦系統，其包含： a·—輪入裝置； b·—輪出裝置； C· 一處理器； O:\91\9I145.DOC -12- d· 一記憶體； •針對一作業系統之程式設計； f •用於決定序列對齊分數之程式設計； g. 用於儲存絲取複數個序列與序列對齊分數之程式設計；及 0 t針對如巾請專難圍第7項之方法之程式設計。 .一種電腦系統，其包含： a· 一輪入裝置； b•一輪出裝置； e· 一處理器； d· 一記憶體； e·針對一作業系統之程式設計； f •用於決定序列對齊分數之程式設計； g用於儲存亚擷取複數個序列與序列對齊分數之程式設计；及 h. 針對如巾請專利範圍第12項之方法之程式設計。 50· 一種電腦系統，其包含： a_ —輪入裝置； b•一輸出裝置； C· 一處理器； d· 一記憶體； e.針對一作業系統之程式設計； f•用於決定序列對齊分數之程式設計； gi於儲存並擷取複數個序列與序列對齊分數之程式設 O:\91\91I45.DOC -13, 計；及 51 針對如申請專利範圍第17項之方法之程式設計。種電腦系統，其包含： a· 一輪入裝置； b·—輪出裝置； e· 一處理器； d•一記憶體； e’針對一作業系統之程式設計； •用於決定序列對齊分數之程式設計；用於儲存並擷取複數個序列與序列對齊分數之程式設計；及 t針對如申請專利範圍第19項之方法之程式設計。種電腦系統，其包含： a·—輸入裝置； b•一輪出裝置； e·—處理器； d· 一記憶體；針對一作業系統之程式設計； f•用於決定序列對齊分數之程式設計； g用於儲存並擷取複數個序列與序列對齊分數之程式設計；及十對如申凊專利範圍第24項之方法之程式設計。 53. —種電腦系統，其包含： a· 一輸入裝置； O:\91\91U5 DOC -14- 一輪出裝置；一處理器； b. c. d· 一記憶體； e•針對一作業系統之程式設計； f.用於決定序列對齊分數之程式設計；用於儲存並擷取複數個序列與序列對齊分數之程式設計；及 5 ^針對如申請專利範圍第29項之方法之程式設計。 54·—種電腦系統，其包含： a· 一輪入裝置； b·—輪出裝置； e·—處理器； d·—記憶體； e•針對一作業系統之程式設計； f. 用於決定序列對齊分數之程式設計； g. 用於儲存並擷取複數個序列與序列對齊分數之程式設計；及 h. 針對如申請專利範圍第34項之方法之程式設計。 5 5 ·_種電腦系統，其包含： a·—輸入裝置； b·—輸出裝置； c· 一處理器； d· 一記憶體； e•針對一作業系統之程式設計； 0:\91\91145.d〇c -15- 用於決定序列對齊分數之程式設計；用於儲存並操取複數個序列與序列對齊分數之程式設計；及 % t針對如申請專利範圍第36項之方法之程式設計。 •〜種電腦系統，其包含： a·—輪入裝置； b•一輪出裝置； e·—處理器； d·—記憶體； ’針對一作業系統之程式設計；用於決定序列對齊分數之程式設計； 8用於儲存並擷取複數個序列與序列對齊分數之程式設計；及 π t針對如申請專利範圍第41項之方法之程式設計。 .—種電腦系統，其包含： ^ 一輪入裝置； b·—輪出裝置； e· —處理器； d· 一記憶體； e.針對一作業系統之程式設計； •用於決定序列對齊分數之程式設計；用於儲存並擷取複數個序列與序列對齊分數之程式設計；及 > & h.針對如中請專利範圍第46項之方法之程式設計。 O:\91\9I145 DOC -16-