{"id":"W4306735589","doi":"10.1101/2022.10.14.512303","title":"Sequence aligners can guarantee accuracy in almost <i>O</i> ( <i>m</i> log <i>n</i> ) time: a rigorous average-case analysis of the seed-chain-extend heuristic","year":2022,"lang":"en","type":"preprint","venue":"bioRxiv (Cold Spring Harbor Laboratory)","topic":"Genomics and Phylogenetic Studies","field":"Biochemistry, Genetics and Molecular Biology","cited_by":3,"is_retracted":false,"has_abstract":true,"ca_institutions":"The Scarborough Hospital; University of Toronto","funders":"","keywords":"Chaining; Substring; Sequence (biology); Speedup; Chain (unit); Conjecture; Heuristic; Algorithm; Computer science; Combinatorics; Upper and lower bounds; Quadratic equation; Heuristics; Mathematics; Discrete mathematics; Parallel computing; Data structure; Mathematical optimization; Physics","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.009214379,0.001536517,0.002233632,0.001133927,0.001212541,0.003134015,0.003112334,0.002542101,0.004997763],"category_scores_gemma":[0.05145884,0.001086119,0.00162705,0.001622801,0.002739923,0.007400078,0.00317081,0.003135532,0.001845348],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002222205,"about_ca_system_score_gemma":0.003072011,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001396801,"about_ca_topic_score_gemma":0.002070491,"domain_scores_codex":[0.9918467,0.00220894,0.0006455432,0.001837184,0.002216676,0.001244867],"domain_scores_gemma":[0.9391603,0.03699898,0.004334541,0.01569747,0.00210393,0.001704835],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.002685884,0.0006600265,0.01435631,0.0007836274,0.0003075663,0.0004074632,0.0004922053,0.6344536,0.06900604,0.07297105,0.01010719,0.193769],"study_design_scores_gemma":[0.00006050143,0.0002672459,0.0009762146,0.00003115065,0.00004854834,0.0002434167,0.00006889542,0.9540096,0.01485225,0.0281352,0.001279038,0.0000280085],"study_design_candidate":"simulation_or_modeling","study_design_consensus":"simulation_or_modeling","genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.1650311,0.001868819,0.8165402,0.001867626,0.0001214517,0.0001806131,0.0004581583,0.006463388,0.007468548],"genre_scores_gemma":[0.6646783,0.0004231226,0.3307552,0.0005060452,0.000189851,0.0001736418,0.0004178554,0.001045754,0.001810205],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.009214379,"threshold_uncertainty_score":0.04873091,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01071714816670514,"score_gpt":0.2234799142444596,"score_spread":0.2127627660777545,"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."}}