新算法助力大規模多序列比對

2020-11-23 科學網

新算法助力大規模多序列比對

作者：

小柯機器人

發布時間：2019/12/3 12:33:22

近日，西班牙巴塞隆納科學技術學院Cedric Notredame、Evan Floden等研究人員合作開發了可用於大規模多序列比對（MSA）的算法。相關論文於12月2日在線發表於《自然—生物技術》。

研究人員引入了一種回歸算法，該算法可在標準工作站上實現多達140萬個序列的MSA，並大大提高了大於10000個序列的數據集的準確性。這一回歸算法與漸進算法相反，以比對最相似的序列為起點。它使用有效的分而治之策略在線性時間內運行第三方對齊方法，而不管其原始複雜性如何。

這一方法將能夠分析非常龐大的基因組數據集，例如最近宣布的地球生物基因組計劃（包含150萬個真核生物基因組）。

據悉，MSA用於結構和進化預測，但是比對大型數據集的複雜性要求使用近似解，包括漸進算法。漸進式MSA方法從比對最相似的序列開始，然後根據引導樹從葉節點到根節點合併其餘序列。隨著序列數量的增加，它們的準確性會大大下降。

附：英文原文

Title: Large multiple sequence alignments with a root-to-leaf regressive method

Author: Edgar Garriga, Paolo Di Tommaso, Cedrik Magis, Ionas Erb, Leila Mansouri, Athanasios Baltzis, Hafid Laayouni, Fyodor Kondrashov, Evan Floden, Cedric Notredame

Issue&Volume: 2019-12-02

Abstract: Multiple sequence alignments (MSAs) are used for structural1,2 and evolutionary predictions1,2, but the complexity of aligning large datasets requires the use of approximate solutions3, including the progressive algorithm4. Progressive MSA methods start by aligning the most similar sequences and subsequently incorporate the remaining sequences, from leaf to root, based on a guide tree. Their accuracy declines substantially as the number of sequences is scaled up5. We introduce a regressive algorithm that enables MSA of up to 1.4 million sequences on a standard workstation and substantially improves accuracy on datasets larger than 10,000 sequences. Our regressive algorithm works the other way around from the progressive algorithm and begins by aligning the most dissimilar sequences. It uses an efficient divide-and-conquer strategy to run third-party alignment methods in linear time, regardless of their original complexity. Our approach will enable analyses of extremely large genomic datasets such as the recently announced Earth BioGenome Project, which comprises 1.5 million eukaryotic genomes6.

DOI: 10.1038/s41587-019-0333-6

Source: https://www.nature.com/articles/s41587-019-0333-6

相關焦點

  • 多序列比對——Clustal
    多序列比對是對3個以上生物序列（蛋白質、DNA、RNA等）進行比對,分析序列的同源性，根據比對的結果來構建系統進化樹。
  • 序列比對軟體
    今天小編特意給大家整理分享了有關序列比對綜合分析的軟體，聰明的你們快來試試有沒有心儀的軟體工具。Geneious         序列綜合分析軟體（https://www.geneious.com/）ClustalW  2.1用來對核酸與蛋白序列進行多序列比對（multiple sequence alignment
  • 序列比對及Blast的應用
    早期的序列比對是全局的序列比較，但由於蛋白質具有的模塊性質，可能由於外顯子的交換而產生新蛋白質，因此局部比對會更加合理。通常用打分矩陣描述序列兩兩比對，兩條序列分別作為矩陣的兩維，矩陣點是兩維上對應兩個殘基的相似性分數，分數越高則說明兩個殘基越相似。
  • 常用在線序列比對工具
    序列比對算法。>該主頁提供了多款多序列比對工具，其中Clustal Omega結果形式是全局比對形式，但是算法還是局部比對算法，不建議在分子進化樹分析過程使用Clustal相關程序，因為其速度及準確度均遜色於下述的MAFFT及MUSCLE。
  • 【陪你學·生信】九、多序列比對-Multiple Sequence Alignment(MSA)
    系統發育分析——Phylogenetic Analysis如果選擇合適的序列進行多序列比對，可以分析他們的系統發育關係。，這樣可以提供很多信息；（3）多序列比對選用10-15條序列開始比對（如果10條的結果不錯，又想再加別的序列進行分析也可以。
  • 如何進行基因組序列比對?
    、詳細信息及下載地址已經知道啦，那麼我們來看看利用什麼軟體或算法來將測序數據比對到31億鹼基序列上呢？>BWA-MEM算法可用於reads長度在70 bp~1 Mb的測序數據；而相對BWA-SW，該算法更快更準確；相對於BWA-ALN算法，在70 bp~100 bp的reads比對中，該算法也有更好的性能。
  • 多重序列比對(MSA)分析工具怎麼選,看這一篇就夠了
    原本以為可以快速地進行下一步的選擇壓力分析，沒想到卻在多序列比對這一環節出現了棘手的問題。以前，我都是經過PRANK軟體進行多序列比對，然後再使用Gblocks軟體對數據進行過濾的。現在，由於師弟師妹在拼接CDS序列時，有些鹼基並不是保留3的倍數，造成很多編碼序列出現移碼突變，甚至變成了偽假基因（幾百個基因）。
  • 序列比對綜合分析軟體
    Geneious 8.0.3序列綜合分析軟體；MACAW 2.05多序列構建與分析軟體。Clustal W 2.1用來對核酸與蛋白序列進行多序列比對（multiple sequence alignment）的軟體。FASTA 36.3.6f。將一條序列與另一條序列進行比較或在資料庫中查找同源序列並輸出。
  • 序列比對在biopython中的處理
    序列比對是生物信息學分析中的常見任務，包含局部比對和全局比對兩大算法，局部比對最經典的代表是blast, 全局比對則用於多序列比對。在biopython中，支持對序列比對的結果進行讀寫，解析，以及運行序列比對的程序。
  • 多序列比對分析-Dnaman很好用!
    軟體主要功能匯總1、DNA序列轉化、翻譯2、多序列比對分析3、系統進化樹分析4、DNA序列組裝和編輯5、BLAST通過網絡界面在Intranet / Internet Server上進行搜索6、SiRNA選擇器7、限制性內切酶酶切分析8、翻譯和密碼子使用分析9、蛋白質疏水性/
  • 科學家發明蛋白序列比對新工具
    來自德國慕尼黑大學的研究人員發表了題為「HHblits: lightning-fast iterative protein sequence searching by HMM-HMM alignment」的文章，介紹一種能提高蛋白序列比對分析的新工具
  • 阿里雲高效基因序列檢索助力新冠肺炎病毒序列快速分析
    簡介： 阿里雲高效基因序列檢索助力新冠肺炎病毒序列快速分析AnalyticDB for MySQL是雲端託管的PB級高並發低延時數據倉庫，通過AnalyticDB for MySQL向量檢索功能構建基因檢索系統，支持毫秒級針對10億級別的向量數據進行查詢分析，更加快速、高效地為新冠肺炎病毒防控、研發治療藥物以及相關疫苗提供幫助。
  • 如何獲取蛋白序列並進行序列比對?
    今天我們就來說一下具體的方法，先介紹蛋白序列的獲取和序列比對。以Sox家族的蛋白為例，我們首先通過Uniprot資料庫（http://www.uniprot.org/）獲取蛋白序列：這是打開後是序列，我們看到包括了Sox9，Sox2，Sox11等蛋白的序列，這樣我們就拿到Sox家族的各條序列了，接來下我們進行序列比對。
  • BBRC:章張團隊研究開發出DNA序列並行比對新工具
    最近，中國科學院北京基因組研究所基因組科學與信息重點實驗室「百人計劃」章張研究員，帶領其團隊成功開發出「編碼蛋白質DNA序列並行比對工具—ParaAT（Parallel Alignment and back-Translation）」。
  • 動植物有統一DNA序列
    近期來自密蘇裡大學的多學科研究人員發表了題為「Long Identical Multispecies Elements in Plant and Animal Genomes」的文章，利用開創性的計算機算法，直面迎擊大型數據的挑戰，發現了不同植物和動物物種中統一的DNA序列。
  • 乾貨時間 | 序列比對,科研必備的幾款軟體!
    E可以限定查詢序列中的某個片段，比如「from 200 to 600」就是查詢200-600bp位置的序列 G可以選擇進行多序列比對，並且可以更改序列輸入方式
  • 深蘭科學院基礎研究厚積薄發,「長序列比對算法」助攻戰「疫」
    近日深蘭科學院深度學習科學家方林博士在比對武漢新冠病毒與其他病毒（比如SARS）基因片段時，便利用了計算機科學中的next 值概念和相關算法大大提高了長序列對比的速度。用普通方法，長序列比對的時間複雜度是，這使得長序列比對十分耗時。
  • Nat Methods:蛋白序列比對新工具HHblits更快更準
    近日，來自德國慕尼黑大學的研究人員在Nature Methods雜誌上發表論文"HHblits: lightning-fast iterative protein sequence searching by HMM-HMM alignment"介紹一種能提高蛋白序列比對分析的新工具：HHblits，這是一種能極大增加蛋白功能性分析技術的軟體，能通過新穎的序列尋找方法
  • 手把手教你用DNAMAN進行多序列比對
    今天，小白君繼續給大家講解前天分享的SCI文章（可點擊公眾號-查看歷史消息，閱讀此文章）中所用到的另一個入門級生物信息學技能——用DNAMAN進行多序列比對
  • Methods:德發明蛋白序列比對新工具——HHblits
    近日，德國慕尼黑大學的研究人員發表論文介紹一種能提高蛋白序列比對分析的新工具：HHblits。相關成果公布在《自然—方法學》（Nature Methods）雜誌上。所以蛋白結構分析是蛋白研究的一個重要方面，蛋白結構比對也成為了常規手段之一，研究人員常常在公眾資料庫中比對蛋白結構，通過分析這些相似的已知結構來分析蛋白的功能，S？ding博士說，「這種序列分析方法是生物信息學領域的一種基礎研究手段。」序列尋找程序能通過計算配對方式來評估序列相似性——兩個胺基酸序列被按照先後順序排列，這是根據常見識別，或者同樣方式的胺基酸配對。