FASTA
![ikona](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/48px-Broom_icon.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Preferences-system.svg/16px-Preferences-system.svg.png)
FASTA je sada programů umožňující alignment (srovnávání) sekvencí DNA a proteinů. FASTA je zkratka od slovního spojení „fast alignment“.[1] FASTA programy za využití rychlých, heuristických metod umožňují vyhledat podobné úseky v sekvencích srovnáváním dotazované sekvence se sekvencemi v proteinových a DNA databázích. Další programy poskytují informace o statistické významnosti alignementu.
FASTA se využívá například k odvození funkčních a evolučních vztahů mezi sekvencemi nebo k identifikaci členů genové rodiny.[2]
O programu FASTA jeho tvůrci prohlašují, že se jedná o nejen vysoce selektivní ale zároveň rychlý bioinformatický nástroj. FASTA dokáže získat výsledky s použitím databáze s 2,5 miliony záznamů za méně než 20 minut, což je pozitivní změna oproti programům na bázi NWS. (Naopak metoda BLAST je rychlejší). Sensitivita je dána zejména použitím skórovací tabulky PAM250. Autoři přímo upozorňují, že výsledky získané pomocí programu FASTA nemusejí být vždy jednoznačné a je vždy potřeba je kriticky analyzovat. S tím, jak se metody alignmentu stávají více sensitivní, tím častěji u nich může docházet k chybám.[3]
Historie
Tento software byl poprvé pod názvem FASTP představen Davidem J. Lipmanem a Williamem R. Pearsonem v roce 1985. Původní program FASTP byl sestrojen pro srovnávání a hledání podobností v sekvencích proteinů.[2]
Pearson působí jako profesor na University of Virginia. Lipman je ředitelem NCBI a National Institutes of Health.
V roce 1988 Lipman a Pearson představili program FASTA – jednalo se přepracovanou verzi programu FASTP, která na rozdíl od původního programu umožnila například porovnávání sekvencí DNA nebo srovnání sekvence proteinu se sekvencí DNA (pomocí translace resp. přeložení DNA sekvence), a také poskytla sofistikovanější program pro výpočet statistické významnosti.[4]
FASTA poté procházela dalším vývojem a dnes zahrnuje celou řadu programů umožňujících prohledávání proteinových a nukleotidových databází.
FASTA dnes
V dnešní době sada programů FASTA obsahuje programy pro srovnávání proteinové sekvence s jinou proteinovou sekvencí případně proteinovou databází a stejně tak pro srovnávání nukleotidových sekvencí. Programy pod názvy FASTX a FASTY umožňují srovnat dotazovanou DNA sekvenci s proteinovou databází tak, že sekvenci přeloží ve všech možných čtecích rámcích.
Navíc byly přidány programy využívající i jiné než rychlé heuristické metody hledání – například program SSEARCH srovnávající proteinovou nebo DNA sekvenci s databází za použití Smith-Watermanova algoritmu nebo program GGSEARCH využívající metodu dynamického programování pro sestavení globálního alignementu.[5]
Velký důraz klade FASTA na přesný výpočet statistik podobnosti, aby uživatel mohl rozpoznat, zda došlo k zarovnání pouze náhodou nebo lze na jeho základě předpokládat, že sekvence jsou homologní.
Ze sady programů FASTA vychází také FASTA formát, který slouží k zápisu nukleotidové nebo proteinové sekvence. Sekvence ve FASTA formátu se skládá z jedno-řádkového popisu, po kterém následují data. Popis vždy začíná znakem „větší než“ – tedy „>“. [6] FASTA formát se využívá jako vstupní formát sekvencí při práci z programy FASTA a je hojně využíván i dalšími softwary určenými pro prohledávání databází a vytváření alignementů. Mezi ně patří NCBI (gi), SWISS-PROT (sp) a další.[1]
FASTA program umí pracovat i s jinými formáty, než je přímo FASTA formát. Patří mezi ně: NBRF/PIR, EMBL či GENEBANK full-tape formát.[7]
Metoda vyhledávání
FASTA funguje tak, že vezme zadanou nukleotidovou nebo aminokyselinovou sekvenci a prohledá příslušnou databázi za použití místního sekvenčního alignmentu za účelem nalezení shody v podobných sekvencích v databázi.
Program FASTA využívá z velké části heuristickou metodu, která přispívá k vysoké rychlosti, s jakou pracuje. Nejprve sleduje vzor shod ve slovech, dále shody slov o dané délce a poté označí potenciální shody. Následně provede časově náročnější optimalizované hledání za použití algoritmu Smith-Watermanova typu.
Velikost, kterou bere jako jedno slovo, daná parametrem ktup, udává citlivost a rychlost programu. Zvýšení hodnoty ktup snižuje počet nalezených náhodných shod. Podle shody slov, které program dostane, hledá segmenty, které obsahují seskupení shod blízko sebe. Následně tyto segmenty prověřuje jako možnou shodu.
Postup vyhledávání
Existují určité rozdíly mezi fastn (nukleotidové sekvence) a fastp (proteinové sekvence) související s typem použité sekvence, ale oba programy pracují ve čtyřech krocích a vypočítávají tři skóre, aby popsaly a naformátovaly výsledky sekvenční podobnosti. Jsou to:
Identifikace oblastí s nejvyšší hustotou shod v každém sekvenčním srovnání.
ktup je položeno rovno 1 nebo 2. V tomto kroku jsou nalezeny všechny nebo alespoň část identit mezi dvěma sekvencemi pomocí vyhledávací tabulky. Hodnota ktup určuje, kolik po sobě jdoucích identit je potřeba k tomu, aby byla daná část prohlášena za shodu. To znamená, že čím nižší je ktup hodnota, tím citlivější je hledání. Při použití proteinové sekvence se většinou používá ktup=2, u nukleotidových sekvencí je ktup 4 nebo 6. Krátké oligonukleotidy jsou většinou analyzovány s ktup=1. Program poté najde všechny místní podobnosti (reprezentovány jako diagonály určité délky v dot plotu) mezi dvěma sekvencemi, tak že započítá shody v ktup a zároveň penalizuje zasahující neshody. Tímto způsobem jsou lokální oblasti s vysokou hustotou shod v diagonále odděleny od náhodných shod. U proteinových sekvencí se ke skórování shod v ktup používají hodnoty ze skórovací tabulky BLOSUM50. To zajišťuje, že skupiny identit s vysokým skóre podobnosti přispívají k místnímu diagonálnímu skóre více než identity s nízkým skóre podobnosti. U nukleotidových sekvencí se používá skórovací matice ze stejného důvodu. Poté je vybráno 10 nejlepších lokálních oblastí ze všech diagonál, jsou dány dohromady a uloženy.
Opětovné skenování vybraných oblastí pomocí skórovací matice.
Odstřižení konců oblastí tak, aby obsahovaly pouze ty přispívající k nejvyššímu skóre. V dalším kroku se znovu skenuje vybraných 10 oblastí. K vytvoření nového skóre se použije vhodná skórovací matice, aby se umožnilo hledání shod kratších než hodnota ktup. Během vytváření skóre se také uvažují konzervativní nahrazení, které přispívají ke skóre podobnosti. I když se u proteinových sekvencí používá zejména matice BLOSUM50, program může také použít skórovací matice založené na minimálním počtu záměn bází vyžadovaný pro specifické nahrazení, matice založené pouze na identitách nebo matice využívající alternativní měření podobnosti (PAM). Pro každou oblast na diagonále, která je takto znovu oskórována, je identifikována podoblast s maximálním skóre. Původní skóre nalezené v kroku 1 je použito k seřazení sekvencí z knihovny. Nejvyšší skóre je označeno jako init1.
Spojení oblastí s vysokým skóre
Pokud je v alignmentu nalezeno několik původních oblastí se skórem větším než je hraniční hodnota, zkontroluje se, zda se mohou sestřižené původní oblasti spojit, aby vytvořily přibližný alignment s mezerami. Poté je vypočítáno skóre podobnosti, které je součtem spojených oblastí, mezery jsou přitom penalizovány ztrátou 20 bodů. Toto původní skóre podobnosti (initn) se použije k seřazení sekvencí z knihovny. Skóre jediné nejlepší původní oblasti nalezené v kroku 2 je označeno init1. V tuto chvíli program spočítá optimální alignment původních oblastí jako kombinace kompatibilních oblastí s maximálním skóre. Optimální alignment původních oblastí může být rychle spočítán pomocí dynamických programovacích algoritmů. Výsledné skóre initn je použito k seřazení sekvencí z knihovny. Tento spojovací proces zvyšuje citlivost, ale snižuje selektivitu. Pečlivě spočítaná hraniční hodnota je poté použita ke kontrole. Tato hodnota odpovídá zhruba součtu očekávaného průměrného skóre nepříbuzných sekvencí z knihovny a směrodatné odchylky. Například pro sekvenci o 200 zbytcích za použitého ktup=2 odpovídá tato hodnota 28.
Použití pásmového Smith-Watermanova algoritmu k výpočtu optimálního skóre pro alignment.
Tento krok používá pásmový Smith-Watermanův algoritmus k vytvoření optimalizovaného skóre (opt) pro každý alignment zadané sekvence se sekvencí z knihovny. Ke spočtení optimálního alignmentu slouží pás o 32 zbytcích se středem v regionu init1 (z kroku 2). Poté, co jsou všechny sekvence nalezeny, program vynese původní skóre každé sekvence z knihovny do histogramu a vypočítá statistickou významnost opt skóre. U proteinových sekvencí je konečný alignment vytvořen pomocí úplného Smith-Watermanova alignmentu. U nukleotidových sekvencí se používá pásmový alignment.
Přehled FASTA programů a jejich srovnání
FASTA programy nacházejí oblasti místní nebo globální podobnosti mezi proteinovými nebo nukleotidovými sekvencemi buď prohledáváním v odpovídajících databázích, nebo díky identifikaci místních duplikací v rámci sekvence. Jiné programy poskytují informace o statistické významnosti alignmentu. Stejně jako BLAST, FASTA může být využita k odhadnutí funkčních a evolučních vztahů mezi sekvencemi a může také pomoci identifikovat členy genových rodin.
- FASTP – původní verze, při výpočtu používá pouze jediný nejlepší iniciační region.
- FASTA program je nejvíce citlivý ze všech verzí vzniklých z původního FASTP programu. Liší se jediným přidaným krokem ve výpočtu alignmentu.[1]
Porovnává dvě proteinové sekvence navzájem, nebo protein s proteinovou databází. Dále umí porovnávat i DNA sekvence.[2]
- LFASTA je vhodný k nalezení více lokálních shod mezi dvěma sekvencemi. K zobrazení výsledků využívá "grafickou matrix". Rozdíl mezi FASTA a LFASTA spočívá v zahájení výpočtu. Iniciační region oba programy hledají stejně, FASTA si ale nechává v paměti pouze deset nejlepších. LFASTA ukládá všechny nalezené diagonální regiony které mají skóre vyšší než určený práh.
Oba programy jsou psané v programovacím jazyku C.[1]
- FASTAX /FASTAY porovnávají dvě DNA sekvence mezi sebou nebo databází. DNA je překládána ve třech čtecích rámcích[2]
- TFASTA používá se pokud si nejsme jisti ve kterém čtecím rámci je protein translatován. Přeloží se všech šest možných čtecích rámců, které se následně porovnávají s proteinovými databázemi nebo s databázemi s translatovanou DNA.[7] Existuje v mutacích TFASTY/TFASTX
- SSEARCH - Jedná se o alignment jak DNA tak proteinů pomocí přísného Smith-Waterman algoritmu.
- GGSEARCH využívá metodu dynamického programování pro sestavení globálního alignementu.
- FASTS/TFASTS porovnává set kratších peptidů s databázemi.
- PRSS/ PRFX používají metodu Monte Carlo. [2]
Reference
- ↑ a b c d LESK, Arthur. Introduction to Bioinformatics. Oxford: Oxford university press, 2005. druhá. ISBN 0199277877.
- ↑ a b c d e FASTA Sequence Comparison at the U. of Virginia [online]. [cit. 2014-05-12]. Dostupné z: http://fasta.bioch.virgini[nedostupný zdroj]a.edu/fasta_www2/fasta_list2.shtml
- ↑ Lipman, DJ; Pearson, WR (1985). "Rapid and sensitive protein similarity searches". Science 227 (4693): 1435–41. doi:10.1126/science.2983426. PMID 2983426
- ↑ Pearson, WR; Lipman, DJ (1988). "Improved tools for biological sequence comparison". Proceedings of the National Academy of Sciences of the United States of America 85 (8): 2444–8. doi:10.1073/pnas.85.8.2444. PMC 280013. PMID 3162770
- ↑ The European Bioinformatics Institute [online], FASTA, [cit. 2014-5-12]. Dostupné z: http://www.ebi.ac.uk/Tools/sss/fasta/help/index-protein.html
- ↑ Genomatix [online], DNA sequence formates, [cit. 2014-5-12]. Dostupné z: http://www.genomatix.de/online_help/help/sequence_formats.html Archivováno 17. 4. 2014 na Wayback Machine.
- ↑ a b PEARSON, William. Using the FASTA Program to Search Protein and DNA Sequence Databases. Computer Analysis of Sequence Data. roč. 1994. Dostupné z: http://link.springer.com/protocol/10.1385/0-89603-246-9:307