{"id":"W4361298788","doi":"10.1101/gr.277637.122","title":"Proving sequence aligners can guarantee accuracy in almost <i>O</i> ( <i>m</i> log <i>n</i> ) time through an average-case analysis of the seed-chain-extend heuristic","year":2023,"lang":"en","type":"article","venue":"Genome Research","topic":"Genomics and Phylogenetic Studies","field":"Biochemistry, Genetics and Molecular Biology","cited_by":14,"is_retracted":false,"has_abstract":true,"ca_institutions":"The Scarborough Hospital; University of Toronto","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Combinatorics; Substring; Chaining; Sequence (biology); Chain (unit); Upper and lower bounds; Mathematics; Algorithm; Discrete mathematics; Physics; Biology; Computer science; Data structure; Mathematical analysis; Genetics","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001526764,0.0002182971,0.0003600025,0.0002682219,0.0003295105,0.00004635853,0.0006744736,0.000131186,0.00001905325],"category_scores_gemma":[0.0003602263,0.0001783295,0.0001877903,0.002355503,0.0003920619,0.000003536288,0.000730527,0.0002550785,0.00001588746],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00005583387,"about_ca_system_score_gemma":0.0002751663,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001349418,"about_ca_topic_score_gemma":0.001358883,"domain_scores_codex":[0.9972662,0.0004465876,0.0004182451,0.0006753642,0.0004329761,0.0007605819],"domain_scores_gemma":[0.998356,0.0001869152,0.0001177362,0.0009870698,0.0002707598,0.00008152907],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"bench_or_experimental","study_design_gemma":"bench_or_experimental","study_design_scores_codex":[0.00005850795,0.00007242312,0.00745137,0.00004448127,0.0003672314,0.0002087762,0.001301546,0.009272086,0.9804453,0.00005461985,0.0001678359,0.0005558255],"study_design_scores_gemma":[0.007317343,0.004450378,0.2913702,0.0002945566,0.001954942,0.001366334,0.0162757,0.0436988,0.5134231,0.005559184,0.1090886,0.005200824],"study_design_candidate":"bench_or_experimental","study_design_consensus":"bench_or_experimental","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.9968372,0.0008284759,0.00002055305,0.0004520592,0.00005484196,0.0005419605,0.000543128,0.00000604285,0.0007157185],"genre_scores_gemma":[0.9973418,0.001336049,0.0001268365,0.0001672775,0.00009052046,0.00006847008,0.0001626381,0.00003503382,0.0006714182],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.4670221,"threshold_uncertainty_score":0.7272068,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05970532850008532,"score_gpt":0.3478031844878454,"score_spread":0.2880978559877601,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}