Gap Penalties

9m ago
19 Views
1 Downloads
233.52 KB
19 Pages
Last View : 1d ago
Last Download : 1m ago
Upload by : Farrah Jaffe
Transcription

Gap PenaltiesCMSC 423

General Gap CAThese have the same score, but the second one is often moreplausible.A single insertion of “GAAT” into the first string could changeit into the second. Now, the cost of a run of k gaps is gap k It might be more realistic to support general gap penalty, so thatthe score of a run of k gaps is gap(k) gap k. Then, the optimization will prefer to group gaps together.

General Gap CAPrevious DP no longer works with general gap penalties becausethe score of the last character depends on details of the -Instead, we need to “know” how long a final run of gaps is inorder to give a score to the last subproblem.

Three MatricesWe now keep 3 different matrices:M[i,j] score of best alignment of x[1.i] and y[1.j] ending with a charactercharacter match or mismatch.X[i,j] score of best alignment of x[1.i] and y[1.j] ending with a space in X.Y[i,j] score of best alignment of x[1.i] and y[1.j] ending with a space in Y.8 M [i 1, jM [i, j] match(i, j) max X[i 1, j :Y [i 1, j(M [i, jX[i, j] maxY [i, j(M [iY [i, j] maxX[i1]1]1]k] gap(k)k] gap(k)for 1 k jfor 1 k jgap(k)gap(k)for 1 k ifor 1 k ik, j]k, j]

The M MatrixWe now keep 3 different matrices:M[i,j] score of best alignment of x[1.i] and y[1.j] ending with a charactercharacter match or mismatch.X[i,j] score of best alignment of x[1.i] and y[1.j] ending with a space in X.Y[i,j] score of best alignment of x[1.i] and y[1.j] ending with a space in Y.By definition, alignmentends in a match.8 M [i 1, jM [i, j] match(i, j) max X[i 1, j :Y [i 1, jAny kind of alignment isallowed before the match.AG1]1]1]

The X (and Y) matriceskixG--- ACGT Gyj-k(M [i, jX[i, j] maxY [i, jixyjk] gap(k)k] gap(k)kG--- -CGT Gj-kjk decides how long tomake the gap.We have to make thewhole gap at once in orderto know how to score it.for 1 k jfor 1 k j

The X (and Y) matriceskixG--- ACGT Gyj-k(M [i, jX[i, j] maxY [i, jixyjk] gap(k)k] gap(k)kG--- -CGT Gj-kjk decides how long tomake the gap.We have to make thewhole gap at once in orderto know how to score it.for 1 k jfor 1 k jThis case is automaticallyhandled.kixy---- GCGT Gj-kj

Running Time for Gap Penalties8 M [i 1, jM [i, j] match(i, j) max X[i 1, j :Y [i 1, j(M [i, jX[i, j] maxY [i, j(M [iY [i, j] maxX[i1]1]1]k] gap(k)k] gap(k)for 1 k jfor 1 k jgap(k)gap(k)for 1 k ifor 1 k ik, j]k, j]Final score is max {M[n,m], X[n,m],Y[n,m]}.How do you do the traceback?Runtime: Assume X Y n for simplicity: 3n2 subproblems2n2 subproblems take O(n) time to solve (because we have to try all k)O(n3) total time

Affine Gap Penalties O(n3) for general gap penalties is usually too slow. We can still encourage spaces to group together using a special caseof general penalties called affine gap penalties:gap start the cost of starting a gapgap extend the cost of extending a gap by one more space Same idea of using 3 matrices, but now we don’t need to search overall gap lengths, we just have to know whether we are starting a newgap or not.

Affine Gap Penalties8 M [i 1, j 1]M [i, j] match(i, j) max X[i 1, j 1] match:Y [i 1, j 1]betweenx and y8 gap start gap extend M [i, jX[i, j] max gap extend X[i, j 1] :gap in xgap start gap extend Y [i, j8 gap start gap extend M [iY [i, j] max gap start gap extend X[i :gap in ygap extend Y [i 1, j]If previousalignment ends inmatch, this is anew gap1]1]1, j]1, j]

Affine Gap as Finite State Machinematch(i,j)Mgs gegs gematch(i,j)match(i,j)geYgs gegs geXge

Affine Base Cases (Global) M[0, i] “score of best alignment between 0 characters of x and icharacters of y that ends in a match” - because no such alignmentcan exist. X[0, i] “score of best alignment between 0 characters of x and icharacters of y that ends in a gap in x” gap start i gap extendbecause this alignment looks like:--------yyyyyyyyy X[i, 0] “score of best alignment between i characters of x and 0characters of y that ends in a gap in X” - xxxxxxxxx---------- not allowedM[i, 0] M[0, i] and Y[0, i] and Y[i,0] are computed using the same logicas X[i,0] and X[0,i]

Affine Gap Runtime 3mn subproblems Each one takes constant time Total runtime O(mn): back to the run time of the basic running time.Traceback Arrows now can point between matrices. The possible arrows are given, as usual, by the recurrence. E.g. What arrows are possible leaving a cell in the M matrix?

Why do you “need” 3 matrices? Alternative WRONG algorithm:M[i][j] max(M[i-1][j-1] cost(x[i], y[i]),M[i-1][j] gap (gap start if Arrow[i-1][j] ! ),M[j][i-1] gap (gap start if Arrow[i][j-1] ! ))WRONG Intuition: we only need to know whether we are starting a gap orextending a gap.The arrows coming out of each subproblem tell us how the best alignment ends, so wecan use them to decide if we are starting a new gap.The best alignmentup to this cell endsin a gap.The best alignmentup to this cell endsin a match.PROBLEM: The best alignment for stringsx[1.i] and y[1.j] doesn’t have to be usedin the best alignment betweenx[1.i 1] and y[1.j 1]

Why 3 Matrices: Examplematch 10, mismatch -2, gap -7, gap start -15CARTCA-TOPT(4, 3) optimal score 30 - 15 - 7 8CARTSCA-T-WRONG(5, 3) 30 - 15 - 7 - 15 - 7 -14CARTSCAT--OPT(5, 3) 20 - 2 - 15 - 14 -11this is why we need to keep the X and Y matrices around.they tell us the score of ending with a gap in one of the sequences.

Side Note: Lower Bounds Suppose the lengths of x and y are n. Clearly, need at least Ω(n) time to find their global alignment(have to read the strings!) The DP algorithms show global alignment can be done in O(n2) time.

Side Note: Lower Bounds Suppose the lengths of x and y are n. Clearly, need at least Ω(n) time to find their global alignment(have to read the strings!) The DP algorithms show global alignment can be done in O(n2) time. A trick called the “Four Russians Speedup” can make a similar dynamicprogramming algorithm run in O(n2 / log n) time. We probably won’t talk about the Four Russians Speedup.The important thing to remember is that only one of the four authors is Russian.(Alrazarov, Dinic, Kronrod, Faradzev, 1970) Open questions: Can we do better? Can we prove that we can’t dobetter? No one knows.

Recap Local alignment: extra “0” case. General gap penalties require 3 matrices and O(n3) time. Affine gap penalties require 3 matrices, but only O(n2) time.

What you should know by now. Dynamic programming framework Global & local sequence alignment algorithms with basic gappenalties Alignment with general gap penalties Alignment with affine gap penalties Longest common subsequence (board lecture) Subset Sum (board lecture)

General Gap Penalties Now, the cost of a run of k gaps is gap k It might be more realistic to support general gap penalty, so that the score of a run of k gaps is gap(k) gap k. Then, the optimization will prefer to group gaps together. AAAGAATTCA A-A-A-T-CA AAAGAATTCA AAA----TCA vs. Th

Related Documents:

Traditionally, a skills gap analysis is undertaken using paper-based assessments and supporting interviews; however, technological advancements, such as skill management software, are allowing large companies to administer a skills gap analysis without using a significant proportion of human resources (Antonucci and d’Ovidio, 2012).File Size: 778KBPage Count: 24Explore furtherSkills gap analysis template - Skills for Care - Homewww.skillsforcare.org.uk40 Gap Analysis Templates & Exmaples (Word, Excel, PDF)templatelab.comConducting A Gap Analysis: A Four-Step Templatewww.clearpointstrategy.com(PDF) Gap Analysis - ResearchGatewww.researchgate.net30 FREE Gap Analysis Templates & Examples - TemplateArchivetemplatearchive.comRecommended to you b

3. Statutory Gender Pay Gap Report 2019 In this section is reported the Statutory Gender Pay Gap, the Gender Pay Gap (Excluding Casual Staff), and a review of Bonus Pay. A positive black number, means that there is a pay gap in favour of men, whereas a negative red number means that there is a pay gap in favour of women. 3.1. Statutory Gender .

Gleeds Gender Pay Gap Report 2019 Gleeds figures 2018 PAY GAP This table shows the mean and median pay gap between men and women, based on hourly rates of pay and presented relative to men’s earnings. The median gender pay gap differs from the mean as it shows the mid-point of data, rather than the average. BONUS GAP

GAP Service Quality Model showed the key insights gained through the executive interviews and focus group interviews about the service quality concept. The gaps revealed by the executive interviews were shown in the marketer side (GAP 1, GAP 2, GAP 3, GAP 4), and the GAP 5 which was .

Medicare Readmission Penalties By Hospital, Year 4 Medicare will apply these readmissions penalties to reimbursements from Oct. 1, 2015, through Sept. 30, 2016,

Few existing cost-benefit analyses of criminal penalties There is a large gulf that exists between showing that criminal and civil penalties deter crime and what needs to be done in conducting a cost-benefit analysis. –Obviously if there are costly penalties that don’t deter crime, the cost-benefit

Corporate and Financial Penalties) Act 2019 (Penalties Act) and the Treasury Laws Amendment (Enhancing Whistleblower Protections) Act 2019. The amendments brought about by the Penalties Act which came into effect on 14 March 2019 in particular, will have a substantial impact on

Pay Gap The Gender Pay Gap is a measure designed to show the difference between the gross hourly earnings for all men in an organisation and the gross hourly earnings for all women. In 2019, our mean pay gap was 23.4% compared to 25.5% in 2018 and 26% in 2017. The main driver of the gap continues to be a higher proportion

by law to publish their gender pay gap each year on their own and on the Government’s website. This is Unite the union’s gender pay gap report for 2019 based on 2018 pay. 2 Gender Pay Gap 4 april 2019 ABOUT THIS REPORT The report was prepared in line with the Equality Act 2010 (Gender Pay Gap

The pay gap shows differences in the average (median and mean) earnings between different groups of people by, for example, gender or race. We know that a pay gap will Whole firm Gender Pay Gap 2020 % Dif. to 2019 Median 15.3% –4.7% Mean 32.4% –3.9% Ethnicity Pay Gap 2020 % Dif. to 2019 Median 15.8% 1.9% Mean 36.7% –0.3%

PROGRESS ON THE GENDER PAY GAP: 2019 7 In 2016, we released the first-ever study of the gender pay gap using Glassdoor salary data. In that study, we added to the large body of research confirming the existence of a gender pay gap, but we also used Glassdoor’s unique data to explore the drivers of the pay gap by

report, the 2019 overall pay gap data includes the pay gap data for UK subsidiaries of the firm. Statutory 2019 Gender Pay Gap Reporting The Gender Pay Gap aims to show the distribution of men and women across different roles within an organisation and highlight where there may be concentrations of a particular gender at lower or higher

6 – Gap Analysis Facilitator’s Guide Appendix A: CANDOR Gap Analysis Document Review Checklist Instructions: At least 1 month prior to the onsite gap analysis, collect and provide the following documents for analysis by the Gap Analysis Team. Documents for Submission to Review

tomers (Gap 1); failing to design services that meet expectations (Gap 2); per-formance and service delivery failures (Gap 3); and not communicating service promises accurately (Gap 4). At its most basic level, the logic of the model sug-gests that the Customer Gap

SMS GAP ANALYSIS CHECKLIST AND IMPLEMENTATION PLAN 1. INITIAL GAP ANALYSIS CHECKLIST (TABLE 5-A7-1) 1.1 The initial gap analysis checklist in Table 5-A7-1 can be used as a template to conduct the first step of an SMS gap analysis. This format with its overall “Yes/No/Partial” responses will provide an initial indication of the broad

Skull Gap MARSH: There are no Marsh hexes, only Marsh hexsides. Units must stop after crossing a Marsh hexside. Skull Gap GAP: Mountain hexsides are impassable except where a Gap (pass) is named. Skull Gap RIVER: All river hexsides are impassable except where a marsh, bridge or ford exists, or a temporary Pontoon Bridge (5.41) is built.

2. A/B Test vs. Gap Titan DX (Loop at 100 Watts –Gap at 500 Watts) a. Xmit Reports 1 S Unit From Gap, Receive 1 S Below Gap b. Loop Noise Level 5 Units Gap (Much better copy) 3. Loop has performed well from 30 Watts to 500 Watts 4. Some Commercially Available Magnetic Loop Options a. MFJ

purchase GAP insurance 6 2.6. Add-on GAP insurance purchasers are not a homogeneous group 6 2.7. The remedies may have provided reassurance, but have not yet helped improve knowledge 6 3. Profile of research participants 8 3.1. Car purchase 8 3.2. Demographics 8 3.3. Awareness of GAP insurance 8 3.4. Purchase of GAP insurance 9 3.5.

find more information under "What is excluded under a GAP insurance policy?". 9 These figures apply where the customer is required to pay a motor insurer's excess of 250. Some GAP insurance providers will pay an amount towards this excess. Please check your GAP insurance policy for details. Written off at 6 months Written off at 30 months

Sometimes referred to as a ‘mini-stroke’ or ‘warning stroke’ – an event is defined as a TIA if the symptoms resolve within 24 hours. . 1 in 8 strokes are fatal within the first 30 days. 1 in 4 strokes are fatal within a year. Stroke is the fourth single largest cause of death in the UK and second in the world. By the age of 75, 1 in 5 women and 1 in 6 men will have .